48求条

P1162 填涂颜色

juruolaidayang_AKIOI @ 2024-08-02 16:50:33

#include<bits/stdc++.h>
using namespace std;
const int N=35;
bool vis[N][N];
char mp[N][N];
int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}},n;
struct node{
    int x,y;
};
bool check(int x,int y){
    return x>=0&&x<n&&y>=0&&y<n&&!vis[x][y]&&mp[x][y]=='0';
}
void bfs(int x,int y){
    queue<node> q;
    q.push({x,y});
    vis[x][y]=true;
    while(!q.empty()){
        node t=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int dx=t.x+dir[i][0];
            int dy=t.y+dir[i][1];
            if(check(dx,dy)){
                vis[dx][dy]=true;
                q.push({dx,dy});
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>mp[i][j]; 
        }
    }
    bfs(0,0);
    bfs(0,n-1);
    bfs(n-1,0);
    bfs(n-1,n-1);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(check(i,j)){
                mp[i][j]='2';
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<mp[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

by yunyu2 @ 2024-08-06 11:48:56

#include <bits/stdc++.h>
using namespace std;
int n, a[35][35];
int fx[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
struct pos {
    int x, y;
    pos(int ax = 0, int ay = 0) 
    {
        x = ax;
        y = ay;
    }
};
void bfs(int x, int y) { // 初始坐标是 (x,y),也就是找到边缘的区域
    queue<pos> q;
    if(a[x][y]) // 如果当前位置不是未填色的
        return;
    a[x][y] = 3; // 设置为边缘区域对应的位置
    q.push(pos(x, y));
    while(!q.empty()) {
        pos now = q.front();
        q.pop();
        for(int i = 0; i < 4; i++) {
            int xx = now.x + fx[i][0]; // 下一个点的坐标
            int yy = now.y + fx[i][1];
            if( xx<1 ||yy<1 ||xx>n ||yy>n) // 当下一个点的坐标超出范围
                continue;
            if(a[xx][yy]!=0) // 当下一个点不是 0
                continue;
            a[xx][yy] =3; // 设置为边缘区域对应的位置
            q.push(pos(xx, yy));
        }
    }
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> a[i][j];        
    for(int i=1;i<=n;i++)bfs(1,i);
    for(int i=1;i<=n;i++)bfs(i,n);
    for(int i=1;i<=n;i++)bfs(i,1);
    for(int i=1;i<=n;i++)bfs(n,i); // 遍历最后一列的所有格子
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(a[i][j] == 3)
                cout <<0 << ' '; // 最后输出时的变换
            else if(a[i][j] == 0)
                cout <<2 << ' ';
            else
                cout << 1 << ' ';
        }
        cout << endl;
    }
    return 0;
}

参考代码


by juruolaidayang_AKIOI @ 2024-08-12 15:37:05

@yunyu2 是我的思路错了吗ToT


by yunyu2 @ 2024-08-12 16:35:40

@laixiaoyang 不一定,只是我觉得bfs更好做


by juruolaidayang_AKIOI @ 2024-08-12 16:40:51

@yunyu2 懂了,靴靴


|