HDU 1312 Red and Black（BFS，DFS）

HDU 1312 Red and Black（BFS，DFS）

Red and Black

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 16081    Accepted Submission(s): 9912

Problem 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

Source

​​Asia 2004, Ehime (Japan), Japan Domestic ​​

题解：经典的搜索（bfs，dfs也可以）

TLE代码.....:搜得太深了。。。

#include#include#include#include#include#include#include#include#includetypedef long long LL;using namespace std;int w,h;char z[21][21];int dfs(int i,int j){ if(i<1||j>h||j<1||j>w)return 0; if(z[i][j]!='#') { z[i][j]='#'; return 1+dfs(i-1,j)+dfs(i,j-1)+dfs(i+1,j)+dfs(i,j+1); //TLE.... } else return 0; }int main(){ while(cin>>w>>h){ if(w==0&&h==0)break; for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) cin>>z[i][j]; for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++) if(z[i][j]=='@') cout<

AC代码：（BFS）

#include #include #include #include using namespace std;int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; //扩展的四个方向char map[33][33];int vis[33][33];int n,m;int sum;struct node{ int x,y;}f[333];#define inf 0xfffffffvoid bfs(int x,int y){ int i; queueq; node st,ed; st.x=x; st.y=y; q.push(st); while(!q.empty()) //队列非空 { st=q.front(); q.pop(); for(i=0;i<4;i++) { ed.x=st.x+dir[i][0]; ed.y=st.y+dir[i][1]; if(ed.x>=n ||ed.y>=m ||ed.x<0 ||ed.y<0 ||map[ed.x][ed.y]=='#' ||map[ed.x][ed.y]=='@') //判断越界 continue; map[ed.x][ed.y]='@'; //标志已经遍历过的 sum++; q.push(ed); } }}int main(){ int i,j,x,y; while(scanf("%d%d",&m,&n)!=EOF&&n!=0 &&m!=0) { for(i=0;i

AC代码：（DFS）

#include #include #include using namespace std;int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};char map[33][33];int vis[33][33];int n,m;int sum;#define inf 0xfffffffvoid dfs(int x,int y){ int sx,sy,i; sum++; for(i=0;i<4;i++) { sx=x+dir[i][0]; sy=y+dir[i][1]; if(sx>=n ||sy>=m ||sx<0 ||sy<0 ||map[sx][sy]=='#' ||map[sx][sy]=='@') continue; map[sx][sy]='@'; dfs(sx,sy); } }int main(){ int i,j,x,y; while(scanf("%d%d",&m,&n)!=EOF&&n!=0 &&m!=0) { for(i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。