原题
题目链接
题目大意
题目是讲给一张图,然后这张图里一个'@'的字符表示起点,'.'是黑瓦(可移动到该位置),'#'是红瓦片(不可移到该位置),然后问可以到达的位置有多少个,包括起点.
题目分析
dfs模板题,可以当作练习基本的dfs,读入地图的时候顺便记录起点的位置,然后从起点开始dfs,走过的位置顺便标记为'#',防止重复走,记录走过的步数即可.具体dfs可看代码.
代码
1 #include <cstdio>
2 #include <cmath>
3 #include <iostream>
4 #include <cstring>
5 #include <algorithm>
6 #include <vector>
7 #include <string>
8 #include <utility>
9 #include <queue>
10 #include <stack>
11 const int INF=0x3f3f3f3f;
12 using namespace std;
13
14 char a[20][20];
15 int ans;
16
17 void dfs(int x,int y,int w,int h)
18 {
19 a[x][y]='#'; //到达的地方标记为'#'防止走重复的路
20 ans++; //每走一步ans++
21 int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; //枚举前进方向
22 int nx,ny;
23 for(int k=0;k<4;k++)
24 {
25 nx=x+dx[k],ny=y+dy[k];
26 if(nx>=0&&nx<h&&ny>=0&&ny<w&&a[nx][ny]=='.') dfs(nx,ny,w,h);//防止越界
27 }
28 }
29
30 int main()
31 {
32 int w,h;
33 cin>>w>>h;
34 getchar();
35 while(w&&h)
36 {
37 int i0,j0;
38 ans=0;
39 memset(a,0,sizeof(a));
40 for(int i=0;i<h;i++)
41 for(int j=0;j<w;j++)
42 {
43 cin>>a[i][j];
44 if(a[i][j]=='@') i0=i,j0=j;
45 }
46 dfs(i0,j0,w,h);
47 cout<<ans<<endl;
48 cin>>w>>h;
49 }
50
51 return 0;
52 }
转载于:https://www.cnblogs.com/VBEL/p/10427848.html