dfs
注意这个不可以回溯
标记求所有情况,找到了就要标记。如果取消标记,那么就会重复计算。
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int dx[8]={-1,0,1,1,1,0,-1,-1};
const int dy[8]={-1,-1,-1,0,1,1,1,0};
char g[1001][1001];
int ans,n,m;
bool st[1001][1001];
void dfs(int x,int y)
{
st[x][y]=true;
for(int i=0;i<8;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a>=1&&a<=n&&y>=1&&y<=m&&!st[a][b]&&g[x][y]=='W')
dfs(a,b);
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>g[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(g[i][j]=='W' and !st[i][j])
{
dfs(i,j);
ans++;
}
}
}
cout<<ans;
return 0;
}
bfs
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1010;
typedef pair<int,int> PII;
int n,m;
char farm[N][N];
int dx[8]={1,1,1,0,0,-1,-1,-1};
int dy[8]={1,0,-1,1,-1,1,0,-1};
void bfs(int x,int y)
{
queue<PII> q;
q.push({x,y});
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<8;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(x<0 || y<0 || x>=n || y>=m) continue;
if(farm[x][y]=='W')
{
farm[x][y]='.';//直接修改状态相当于标记
q.push({x,y});
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>farm[i];
int ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(farm[i][j]=='W')
{
bfs(i,j);
ans++;
}
cout<<ans;
return 0;
}