[关闭]
@xunuo 2017-04-14T20:56:24.000000Z 字数 2057 阅读 1178

HDU 1312 Red and Black


Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

BFS


Description

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.

Write a program to count the number of black tiles which he can reach by repeating the moves described above. 

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.

'.' - a black tile 
'#' - a red tile 
'@' - a man on a black tile(appears exactly once in a data set) 

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself). 

Sample Input

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

Sample Output

45
59
6
13

题意:

一块矩形的地面,贴有红色和黑色的地砖,一个人只能走黑色地砖,能走所在地砖的上,下,左,右四个方向的地砖,给你一个图问总共可以走多少块地砖

解题思路:

一个裸的BFS

完整代码:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dir[4][2]={0,1,0,-1,1,0,-1,0};///方向;
  4. int vis[25][25];///标记(走过为1,没走为0);
  5. char a[25][25];///存图;
  6. int m,n,num;///m列,n行,走过num个点;
  7. ///结构体存点的坐标:
  8. struct node
  9. {
  10. int x;
  11. int y;
  12. };
  13. ///从起点开始搜:
  14. int bfs(int x,int y)
  15. {
  16. queue<node>q;
  17. node now,next;
  18. now.x=x;
  19. now.y=y;
  20. q.push(now);
  21. num++;
  22. vis[x][y]=1;
  23. while(!q.empty())
  24. {
  25. now=q.front();
  26. q.pop();
  27. for(int i=0;i<4;i++)
  28. {
  29. int nx=now.x+dir[i][0];
  30. int ny=now.y+dir[i][1];
  31. if(a[nx][ny]=='.'&&vis[nx][ny]==0&&nx>=0&&nx<n&&ny>=0&&ny<m)
  32. {
  33. next.x=nx;
  34. next.y=ny;
  35. num++;
  36. vis[nx][ny]=1;
  37. q.push(next);
  38. }
  39. }
  40. }
  41. return num;
  42. }
  43. int main()
  44. {
  45. int x,y;
  46. while(scanf("%d%d",&m,&n),m+n)
  47. {
  48. num=0;
  49. memset(a,0,sizeof(a));
  50. memset(vis,0,sizeof(vis));
  51. for(int i=0;i<n;i++)
  52. scanf("%s",a[i]);
  53. for(int i=0;i<n;i++)
  54. for(int j=0;j<m;j++)
  55. {
  56. ///找起点:
  57. if(a[i][j]=='@')
  58. {
  59. x=i;
  60. y=j;
  61. }
  62. }
  63. printf("%d\n",bfs(x,y));
  64. }
  65. return 0;
  66. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注