flood fill(洪水灌溉)算法
DFS
设置偏移量,从头搜到黑
#include<iostream>
using namespace std;
#define N 25
char g[N][N];
int n,m;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int dfs(int x,int y)
{
g[x][y] = '#';
int res = 1;
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 || g[a][b] != '.')
continue;
res += dfs(a,b);
}
return res;
}
int main()
{
while(cin>>m>>n , m || n)
{
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;
}
cout<<dfs(x,y)<<endl;
}
}
BFS
再连通块中的四个方向,进行搜索,符合就入队,然后继续通过扩展队列
#include<iostream>
#include<queue>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 25;
char g[N][N];
int m,n;
int bfs(int sx,int sy)
{
queue<PII> q;
q.push({sx,sy});
g[sx][sy] = '#';
int res = 0;
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
while(q.size())
{
auto t = q.front();
q.pop();
res ++;
for(int i = 0;i < 4;i ++)
{
int x = t.x + dx[i] , y = t.y + dy[i];
if(x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '.') continue;
g[x][y] = '#';
q.push({x,y});
}
}
return res;
}
int main()
{
while(cin>>m>>n , n || m)
{
for(int i = 0;i < n;i ++) cin>>g[i];
int x,y;
for(int i = 0;i < n;i ++)
for(int j = 0;j < m;j ++)
if(g[i][j] == '@')
{
x = i;
y = j;
}
cout<<bfs(x,y)<<endl;
}
return 0;
}