题目描述

Flood Fill 算法
DFS/BFS
DFS:宽搜，可求最短距离
BFS:深搜：代码简单

样例

BFS伪代码：
while(队列不空)
{
    取出队头t;
    枚举t的四个邻格
    if（格子是陆地，或者未被开发）  就标记为已被开发
    将新格子插入队列
}
DFS伪代码：
上右下左去拓展
递归处理
{
    将x,y标记为已开发
    枚举x,y的4个邻格
    if(邻格可走)  dfs(邻格)
}

C++ 代码(bfs) O(nm)

#include<queue>
#include<iostream>
#include<algorithm>//需要用到pair
using namespace std;
const int N = 25;
int n,m;
char g[N][N];
int bfs(int sx,int sy)
{
    queue<pair<int,int>> q;//定义一个pair类型的队列
    q.push({sx,sy});//将人所在的位置作为起点放到队列中
    g[sx][sy]='#';//起点已被搜到 标记为障碍物 不能再走
    int res = 0;//表示所有能够搜到的点的数目
    while(q.size())//当队列不空
    {
        pair<int,int> t=q.front();//取出队头元素
        q.pop();//将队头删掉
        res++;//队列里出一个点 就是扩展了一个点
        int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
        for(int i =0;i<4;i++)
        {
            int x=t.first+dx[i],y=t.second+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)//输入及停止条件，注意m,n的顺序 其中m是列，n是行
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin>>g[i][j];//读入数据
        int x,y;//定义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;
}

C++ 代码 dfs

#include<iostream>
using namespace std;
const int N = 25;
int n,m;
char g[N][N];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};

int dfs(int x,int y)
{
    int res = 1;
    g[x][y]='#';//将x,y标记为已开发
    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]=='.')//可走
            res+=dfs(a,b);
    }
    return res;
}
int main()
{
    while(cin>>m>>n,n||m)//输入及停止条件，注意m,n的顺序 其中m是列，n是行
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin>>g[i][j];//读入数据
        int x,y;//定义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<<dfs(x,y)<<endl;//以人所在的位置向四周进行深搜
    }   
    return 0;
}