莫欺少年穷,修魔之旅在这开始—>算法提高课题解
保姆级注释,看不懂你炸我
思路:
1. 多组测试数据,需要不断初始化st数组
2. 找到起点坐标,对其做dfs
3. 记录该点,枚举四个方向,cnt加上符合条件的点继续做dfs得到的数量
#include<bits/stdc++.h>
using namespace std;
const int N = 25;
int n,m;
char g[N][N];
bool st[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int dfs(int x,int y)
{
//该点的初始块
int cnt=1;
//记录该点
st[x][y]=true;
//枚举四个方向
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
//超出边界
if(a<0||a>=n||b<0||b>=m) continue;
//该点不是要找的点或该点已被记录
if(g[a][b]!='.'||st[a][b]) continue;
//加上接下来符合条件的点的数量
cnt+=dfs(a,b);
}
return cnt;
}
int main()
{
while(cin>>m>>n,n||m)
{
memset(st,0,sizeof st);
for(int i=0;i<n;i++) cin>>g[i];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(g[i][j]=='@')
cout<<dfs(i,j)<<endl;
}
return 0;
}