题目

小蓝有一个01矩阵。他打算将第一行第一列的 0 变为 2 。变化过程有传染性，每次 2 的上下 左右四个相邻的位置中的 0 都会变成 2 。直到最后每个 2 的周围都是 1 或 2 结束。 请问，最终矩阵中有多少个 2 ？以下是小蓝的矩阵，共 30 行 40 列。

暴力搜索(dfs)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =45;
char map[N][N];
int cnt;
void dfs(int x,int y)
{
    if(map[x][y]=='1')
    {
        return ;
    }
    else
    {
        cnt++;
        map[x][y]='1';
        dfs(x,y+1);
        dfs(x,y-1);
        dfs(x-1,y);
        dfs(x+1,y);
    }

}
int main()
{
    memset(map,'1',sizeof(map));
    for(int i=1;i<=30;i++)
    {
        for(int j=1;j<=40;j++)
        cin>>map[i][j];
    }
    dfs(1,1);
    cout<<cnt<<endl;
    return 0;
}

第二种暴搜(红与黑模版)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 40;
char map[N][N];
int cnt;
//bool vis[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int dfs(int x, int y)
{
    //vis[x][y] = true;
    map[x][y] = '2'; // 将其标记为 '2'
    int cnt=1;
    for(int i = 0; i < 4; i++)
    {
        int a = x + dx[i];
        int b = y + dy[i];
        if(a >= 1 && a <= 30 && b >= 1 && b <= 40 && map[a][b] =='0')
        {
             cnt+=dfs(a, b);
        }
    }
    return cnt;
}
int main()
{
   // memset(map, 1, sizeof map);
    for(int i = 1; i <= 30; i++)
    {
        for(int j = 1; j <= 40; j++)
        {
            cin >> map[i][j];
        }
    }
    cout << dfs(1, 1) << endl;
    return 0;
}

bfs宽搜(用队列–红与黑模版)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N =45;
char map[N][N];
bool st[N][N];
int cnt;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int bfs(int x,int y)
{
    queue<PII> q;
    q.push({x,y});
    st[x][y]=true;
    int cnt =1;
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int a =t.x+dx[i];
            int b =t.y+dy[i];
            if(a<1||b<1||a>30||b>40||map[a][b]!='0'||st[a][b]) continue;
            st[a][b]=true;
            q.push({a,b});
            cnt++;
        }
    }
    return cnt;
}
int main()
{   
    memset(map,'-1',sizeof(map));
    for(int i=1;i<=30;i++)
    {
        for(int j=1;j<=40;j++)
        {
            cin>>map[i][j];
        }
    }
    cout<<bfs(1,1)<<endl;
    return 0;
}