P1162 填涂颜色 求助(玄关)

P1162 填涂颜色

WHX985 @ 2024-11-03 15:30:06

80pts

#include<iostream>
using namespace std;
int a[1005][1005],u[1005][1005],sx[4]={-1,1,0,0},zy[4]={0,0,-1,1},ax[10005],ay[10005],dep[10005];
int maxn=0x7ffffff;
int n,m;
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++){
        for(int j=1;j<=n;j++){
            bool o=0,o2=0,o3=0,o4=0;
            if(a[i][j]==0){
                for(int h=i;h>=1;h--){
                    if(a[h][j]==1){
                        o=1;
                        break;
                    }
                }
                for(int h=i;h<=n;h++){
                    if(a[h][j]==1){
                        o2=1;
                        break;
                    }
                }
                for(int h=j;h>=1;h--){
                    if(a[i][h]==1){
                        o3=1;
                        break;
                    }
                }
                for(int h=j;h<=n;h++){
                    if(a[i][h]==1){
                        o4=1;
                        break;
                    }
                }
                if(o==1&&o2==1&&o3==1&&o4==1){
                    a[i][j]=2;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}

by Caiyuheng0923 @ 2024-11-03 16:53:24

我用的搜索做,类似洪水算法


#include<bits/stdc++.h>
using namespace std;
int a[35][35],n;
struct ge {
    int x;
    int y;
};
int di[5]= {0,0,0,1,-1};
int dj[5]= {0,1,-1,0,0};
void bfs(int ox,int oy) {
    ge q[1001];
    int head=0,tail=0;
    ge q1;
    q1.x=ox;
    q1.y=oy;
    q[++tail]=q1;
    if(!a[q[tail].x][q[tail].y]) {
        a[q[tail].x][q[tail].y]=2;
    }
    while(head<=tail) {
        head++;
        for(int i=1; i<=4; i++) {
            int newx=q[head].x+di[i];
            int newy=q[head].y+dj[i];
            if(newx>=1&&newx<=n&&newy>=1&&newy<=n&&a[newx][newy]==0) {
                ++tail;
                q[tail].x=newx;
                q[tail].y=newy;
                a[newx][newy]=2;
            }
        }
    }
}
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++) {
        if(a[1][i]==0) bfs(1,i);
        if(a[n][i]==0) bfs(n,i);
        if(a[i][1]==0) bfs(i,1);
        if(a[i][n]==0) bfs(i,n);
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(a[i][j]==2)
                cout<<0<<" ";
            if(a[i][j]==1)
                cout<<1<<" ";
            if(a[i][j]==0)
                cout<<2<<" ";
        }
        cout<<endl;
    }
    return 0;
}

by tengyuxuan @ 2024-11-03 19:59:09

看错题了


by WHX985 @ 2024-12-09 20:55:50

谢谢@tengyuxuan@Caiyuheng0923 虽然过了 【考古】


by tengyuxuan @ 2024-12-10 19:32:18

@WHX985 我得:

#include <bits/stdc++.h>
using namespace std;
int n;
int b[35][35],a[35][35];
void dfs(int x,int y){
    if(x<0||y<0||y>=n+2||x>=n+2||a[x][y]!=0)return;//出界或者搜过的或者是墙就停
    a[x][y]=1;
    dfs(x+1,y);
    dfs(x-1,y);
    dfs(x,y-1);
    dfs(x,y+1);//搜索
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>b[i][j];
            if(b[i][j]==1)a[i][j]=3;//是墙就标记为3(我喜欢)
        }
    }
    dfs(0,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]==0){//没搜过,也就是闭合圈内
                cout<<2<<' ';//输出2
            }else{
                cout<<b[i][j]<<' ';
            }
        }
        cout<<endl;
    }
    return 0;
}

我在外面加了一圈0所以不会搜不到


by WHX985 @ 2024-12-10 20:03:09

大佬

%%%%%%%%


|