题目链接http://ybt.ssoier.cn:8088/problem_show.php?pid=1216
方法一：DFS
1 #include<bits/stdc++.h> 2 using namespace std; 3 int w, h; //h代表行数， w代表列数 4 int sx, sy; //@点，搜索起始位置 5 char mp[25][25]; //存放棋盘形状 6 char c; //用于读入字符 7 int ans; //存放答案 8 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //存储可移动的方向 9 void dfs(int x, int y){ 10 mp[x][y]='#'; //合法搜索后将字符更改，以防重复 11 ans++; //答案累加 12 for(int i=0; i<4; i++){ //四个方向遍历 13 int nx=x+dir[i][0], ny=y+dir[i][1]; //借助dir数组确定方向 14 if(nx>=0 && nx<h && ny>=0 && ny<w && mp[nx][ny]=='.')//判断条件 15 dfs(nx, ny); 16 } 17 } 18 int main() 19 { 20 while(1){ 21 cin>>w>>h; 22 getchar(); //过滤换行符 23 if(w==0 && h==0)break; //结束判断 24 for(int i=0; i<h; i++){ //逐行输入 25 for(int j=0; j<w; j++){ //逐个字符输入 26 c=getchar(); //使用getchar()读入单个字符，注意空格换行都会被读入 27 if(c=='@'){ //找到起始位置存入sx, sy 28 sx=i; sy=j; 29 } 30 mp[i][j]=c; //每个字符存入mp 31 } 32 getchar(); //过滤换行符 33 } 34 // for(int i=0; i<h; i++){ //读入数据输出测试，注意样例中6 9后面有个空格，影响测试结果 35 // for(int j=0; j<w; j++) 36 // cout<<mp[i][j]; 37 // cout<<endl; 38 // } 39 40 ans=0; //每次ans初始化为0 41 dfs(sx, sy); //从@位置开始搜索 42 cout<<ans<<endl; 43 } 44 return 0; 45 }
24-33行输入还可以用以下代码，就不用考虑换行符的问题
1 for(int i=0; i<h; i++)cin>>mp[i]; 2 for(int i=0; i<h; i++){ 3 for(int j=0; j<w; j++) 4 if(mp[i][j]=='@'){ 5 sx=i; sy=j; 6 } 7 }
方法二：BFS
1 #include<bits/stdc++.h> 2 using namespace std; 3 int w, h; //h代表行数， w代表列数 4 int sx, sy; //@点，搜索起始位置 5 char mp[25][25]; //存放棋盘形状 6 char c; //用于读入字符 7 int ans; //存放答案 8 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //存储可移动的方向 9 struct node{ //定义结构体节点存放坐标 10 int x, y; 11 }; 12 node que[500]; //结构体数组对列 13 int f, r; //队首， 队尾 14 void testpr(){ //用于测试观察队列队变化情况 15 for(int i=1; i<=r; i++) 16 cout<<"'"<<que[i].x<<","<<que[i].y<<"'"<<" "; 17 cout<<endl; 18 } 19 void bfs(int x, int y){ 20 memset(que, 0, sizeof(que)); //将队列初始化 21 f=r=1; //队首队尾初始化为1 22 que[r].x=x, que[r].y=y, mp[x][y]='#', ans++; //初始‘@’入队 23 while(f<=r){ 24 node t; 25 t.x=que[f].x, t.y=que[f].y; //获得队首节点信息 26 for(int i=0; i<4; i++){ //队首四个方向遍历 27 int nx=t.x+dir[i][0]; 28 int ny=t.y+dir[i][1]; 29 if(nx>=0 && nx<h && ny>=0 && ny<w && mp[nx][ny]=='.'){//判断条件 30 mp[nx][ny]='#';//更改数据防止重复访问 31 ans++; 32 //testpr(); //用于观察队列变化情况 33 ++r; //队尾后移准备入队 34 que[r].x=nx; //入队 35 que[r].y=ny; //入队 36 } 37 } 38 f++;//出队，队首位置后移 39 } 40 } 41 int main() 42 { 43 while(1){ 44 cin>>w>>h; 45 getchar(); //过滤换行符 46 if(w==0 && h==0)break; //结束判断 47 for(int i=0; i<h; i++){ //逐行输入 48 for(int j=0; j<w; j++){ //逐个字符输入 49 c=getchar(); //使用getchar()读入单个字符，注意空格换行都会被读入 50 if(c=='@'){ //找到起始位置存入sx, sy 51 sx=i; sy=j; 52 } 53 mp[i][j]=c; //每个字符存入mp 54 } 55 getchar(); //过滤换行符 56 } 57 // for(int i=0; i<h; i++){ //读入数据输出测试，注意样例中6 9后面有个空格，影响测试结果 58 // for(int j=0; j<w; j++) 59 // cout<<mp[i][j]; 60 // cout<<endl; 61 // } 62 63 ans=0; //每次ans初始化为0 64 bfs(sx, sy); //从@位置开始搜索 65 cout<<ans<<endl; 66 } 67 return 0; 68 }