红与黑

题解

说明

其实这里考查的是Flood Fill算法(洪水灌溉算法)

Flood Fill 分为两种

• bfs ：可顺便求出最短距离
• dfs : 更为方便，但是题目不严谨时，可能会爆栈
• 题目草图

蓝色表示现在的位置，只可以走黑色，不可以走红色，求可以到达的黑色色块数量。

解法一：宽度搜索优先遍历

思路

1、先定义上下左右四个方向

2、对周围格子进行遍历，然后进入符合的格子

3、循环往复，直到全部格子都被遍历

代码

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

typedef pair<int,int> PII; 
const int N = 22;
char diban[N][N];
int n,m;

bool st[N][N];
int cnt;

//宽搜 
int bfs(int x,int y)//将初始位置输入 
{
    queue<PII> que;
    que.push({x,y});
    st[x][y] = true;
    cnt++;

    //四个方向逐一遍历,上、下、左、右 
    int dx[4] = {-1 , 1 , 0 , 0} , dy[4] = { 0 , 0 , -1 , 1};

    while(que.size())
    {
        //这个位置已经遍历过了，那么取出来
        PII q = que.front(); 
        int qx = q.first , qy = q.second;
        que.pop();

        int tx = 0 , ty = 0;
        //四个方向进行行走
        for(int i = 0 ; i<4 ; i++)
        {
            tx = qx + dx[i] , ty = qy + dy[i];
            //判断是否合理，一是有没有走过，二是符不符合灌溉条件
            if(diban[tx][ty] == '.' && !st[tx][ty] ) //符合 
            {
                 //进行灌溉
                 que.push({tx,ty});
                 st[tx][ty] = true;
                 cnt++; 
            }
        }

    } 
    return cnt;

}

int main()
{
    while(cin >> m >> n, n || m)
    {
        //一切清零，重新开始 
        cnt = 0;//数量清零
        memset(st , false , sizeof st);

        int x = 0, y = 0;//初始位置 
        //输入 
        for(int i = 0 ; i<n ; i++)
            for(int j = 0 ; j<m ; j++)
            {
                cin>>diban[i][j];
                if(diban[i][j] == '@')
                {
                    x = i ;
                    y = j ; 
                }
            }   

        cout<<bfs(x,y)<<endl;
    }

    return 0;
 } 

解法二：深度搜索优先遍历

思路

1、先进行一个方向的遍历

2、然后不可以在这个方向进行遍历了，那么换一个方向进行遍历

3、直到所有方向都不能进行遍历，那么回溯到上一个格子

4、全部格子都被遍历，那么结束

代码

#include<iostream>
#include<cstring>
using namespace std;

const int N = 22;
char diban[N][N];
int n,m;
bool st[N][N];
int cnt;
//深搜 
void dfs(int x,int y) 
{ 
    cnt++;
    //按上、左、下、右，顺序遍历节点
    int dx[] = {-1 , 0 , 1 , 0} , dy[] = { 0 , 1 , 0 , -1};

    //深度搜索 
    for(int i = 0 ; i<4 ; i++)
    {
        int tx = x + dx[i] , ty = y + dy[i];
        if(diban[tx][ty] == '.' && !st[tx][ty] )
        {
            st[tx][ty] = true;
            dfs(tx,ty);
        }
    }

}

int main()
{
    while(cin>>m>>n, n || m)
    {
        //一切清零
        cnt = 0; 
        memset(st , false , sizeof st);
        //初始位置 
        int x = 0 , y = 0;

        for(int i = 0 ; i<n ; i++ )
            for(int j = 0 ; j<m ; j++)
            {
                cin>>diban[i][j];
                if(diban[i][j] == '@')
                    x = i , y = j;
            }

        dfs(x, y);  
        cout<<cnt<<endl;
    }

    return 0;
}