题目描述
dfs 每次dfs到时才做标记
#include <iostream>
using namespace std;
const int N=25;
const int M=25;
char x[N][M];
int n,m;
int res;
int visit[N][M];
int dx[]= {0,1,0,-1};
int dy[]= {1,0,-1,0};
int dfs(int a,int b)
{
int res=1;
x[a][b]='#';
for(int i=0; i<4; i++)
{
int s=a+dx[i];
int t=b+dy[i];
if(s>=0&&t>=0&&s<n&&t<m&&x[s][t]=='.')
{
res+=dfs(s,t);
}
}
return res;
}
int main()
{
while(cin>>m>>n&&n&&m)
{
int a,b;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
cin>>x[i][j];
if(x[i][j]=='@')
a=i,b=j;
}
cout<<dfs(a,b)<<endl;
}
//cout << "Hello world!" << endl;
return 0;
}
题目描述
bfs 注意做标记顺序!!入队时
#include <iostream>
using namespace std;
const int N=25;
const int M=25;
char x[N][M];
int n,m;
int res;
int visit[N][M];
int dx[]= {0,1,0,-1};
int dy[]= {1,0,-1,0};
int dfs(int a,int b)
{
int res=1;
x[a][b]='#';
for(int i=0; i<4; i++)
{
int s=a+dx[i];
int t=b+dy[i];
if(s>=0&&t>=0&&s<n&&t<m&&x[s][t]=='.')
{
res+=dfs(s,t);
}
}
return res;
}
int main()
{
while(cin>>m>>n&&n&&m)
{
int a,b;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
cin>>x[i][j];
if(x[i][j]=='@')
a=i,b=j;
}
cout<<dfs(a,b)<<endl;
}
//cout << "Hello world!" << endl;
return 0;
}