Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 19731 Accepted Submission(s): 11991
1 #include <bits/stdc++.h> 2 using namespace std; 3 int _x[4]={1,0,-1,0}; 4 int _y[4]={0,-1,0,1};//相当于从第一象限开始顺时针转一周,对应的坐标轴上的点分别为(1,0),(0,-1),(-1,0),(0,1),就是数学意义上的方向向量 5 char str[30][30]; 6 bool flag[30][30];//去判断点是否被标记过,DFS搜索一遍,被标记过记改点为1! 7 int n,m,ans; 8 void DFS(int x,int y) 9 { 10 for(int ii=0;ii<4;ii++) 11 { 12 int i=x+_x[ii]; 13 int j=y+_y[ii]; 14 if(i<n&&j<m&&i>=0&&j>=0&&flag[i][j]==0&&str[i][j]==‘.‘)//边界条件 15 { 16 ans++; 17 flag[i][j]=1; 18 DFS(i,j); 19 } 20 } 21 } 22 int main() 23 { 24 while(scanf("%d%d",&m,&n)!=EOF) 25 { 26 if(m==0&&n==0) 27 break; 28 int x,y; 29 memset(flag,0,sizeof(flag)); 30 for(int i=0;i<n;i++) 31 scanf("%s",str[i]); 32 for(int i=0;i<n;i++) 33 { 34 for(int j=0;j<m;j++) 35 { 36 if(str[i][j]==‘@‘)//找到起始点 37 { 38 x=i; 39 y=j; 40 } 41 } 42 } 43 ans=0; 44 flag[x][y]=1; 45 DFS(x,y); 46 printf("%d\n",ans+1);//第一个位置也算一个,所以+1 47 } 48 return 0; 49 }
HDU 1312 Red and Black(DFS,板子题,详解,零基础教你代码实现DFS)
原文:http://www.cnblogs.com/ECJTUACM-873284962/p/6680198.html