AcWing 1113. 红与黑
原题链接
简单
作者:
大雪菜的fans
,
2020-02-26 14:30:02
,
所有人可见
,
阅读 523
参考文献 C++蓝桥杯
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=25;
char g[N][N];
bool st[N][N];
int n,m;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int dfs(int x,int y)
{
int cnt=1;
st[x][y]=1;
for(int i=0;i<4;i++){
// 注意这里要去检查tx/ty,也就是4个方向,而不是x/y
int tx=x+dx[i],ty=y+dy[i];
if(tx<0||tx>=n||ty<0||ty>=m) continue;
if(st[tx][ty])continue;
if(g[tx][ty]!='.')continue;
// 每搜索一次,cnt+1,最后回溯加回来
cnt+=dfs(tx,ty);
}
return cnt;
}
int main()
{
while(cin>>m>>n,n||m)
{
int x,y;
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]=='@')
x=i,y=j;
// 这里记得要清空,每个输入组要清空一次。
memset(st,0,sizeof(st));
printf("%d\n",dfs(x,y));
}
return 0;
}
你好, 每搜索一次,cnt+1,最后回溯加回来 cnt+=dfs(tx,ty); 这一句话不是太明白,他是怎么回溯的