样例4过不去

P1162 填涂颜色

nrkz902 @ 2024-03-05 16:25:32

采用的加一圈0再bfs标记的思路

#include <bits/stdc++.h>
using namespace std;
int n ;
const int N = 40;
int g[N][N];
bool st[N][N];
typedef pair<int , int> PII;
queue<PII> q;
int dx[] = {-1 , 0 , 1 , 0};
int dy[] = {0 , 1 , 0 , -1};

void bfs(int x, int y){
    q.push({x,y});

    while(q.size()){
        auto t = q.front();
        q.pop();
        for(int i = 0 ; i < 4 ; i++){
            int a = t.first + dx[i];
            int b = t.second + dy[i];

            if(a<0 || a>n+1 || b<0 || b>>n+1)
                continue;
            if(st[a][b] == 1)
                continue;
            st[a][b] = 1;
            q.push({a,b});          
        }
    }
}

int main(){
    cin>>n;

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++){
            cin>>g[i][j];
            if(g[i][j] == 1){
                st[i][j] = 1;
            }
        }

    bfs(0 , 0);

    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++){
            if(st[i][j] == 0)
                g[i][j] = 2;
            cout<<g[i][j]<<" ";
        }
        cout<<endl;
    }                            
    return 0;
}

样例4输入如下

20
0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 0 0 1 1 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0

标答输出如下

0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0 
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0 
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0 
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0 
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0 
1 1 1 1 1 2 1 1 1 1 1 1 2 1 0 0 0 0 0 0 
1 2 2 2 2 2 2 2 2 2 2 2 2 1 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 1 2 2 2 2 2 2 2 2 2 2 1 
0 0 0 0 0 0 0 0 1 2 1 1 1 1 2 2 2 1 1 1 
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 1 1 0 0 
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 0 0 0 0 
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 0 0 0 0 
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 1 1 1 1 
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 2 2 2 2 1 
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 1 1 1 1 
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 0 0 0 0 
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 0 0 0 0 
0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 

代码输出答案如下

0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
1 1 1 1 1 2 1 1 1 1 1 1 2 1 0 0 0 0 0 0
1 2 2 2 2 2 2 2 2 2 2 2 2 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 2 2 2 2 2 2 2 2 2 2 1
0 0 0 0 0 0 0 0 1 2 1 1 1 1 2 2 2 1 1 1
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 1 1 0 0
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 0 0 0 0
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 0 0 0 0
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 1 1 1 1
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 2 2 2 2 1
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 1 1 1 1
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 0 0 0 0
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0

by liwenxi114514 @ 2024-03-12 12:59:21

@nrkz902

你的代码能过呀


by nrkz902 @ 2024-03-13 11:02:07

@liwenxi110720 我复制粘贴了还是不行诶 有什么玄学吗 样例4还是wa 关了o2优化345都RE了更不行


by liwenxi114514 @ 2024-03-13 12:38:44

@nrkz902

if(a<0 || a>n+1 || b<0 || b>>n+1)

这里多了一个>,改一下就过了呀


by nrkz902 @ 2024-03-13 21:24:22

@liwenxi110720 orz 居然是这里= = 感谢大佬


|