第5个点TLE

Misaki_Wang @ 2022-07-06 21:07:06

#include<bits/stdc++.h>
using namespace std;
const int maxn=40;

int walk[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
int N;
struct coord{
    int x,y;
};
queue<coord> Q;
int matrix[maxn][maxn];bool vis[maxn][maxn];

void solve(){
    for(int i=2;i<N;++i){
        for(int j=1;j<N;++j){ 
            if(vis[i][j]==false)    matrix[i][j]=2;
            } 
    }
    for(int i=1;i<=N;++i,printf("\n"))  for(int j=1;j<=N;++j) printf("%d ",matrix[i][j]);
}

int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;++i){
        for(int j=1;j<=N;++j) {scanf("%d",&matrix[i][j]);vis[i][j]=true;}}

    for(int i=1;i<=N;++i)   for(int j=1;j<=N;++j) {if(matrix[i][j]==1){Q.push(coord{i+1,j+1});i=j=N;}}

    while(!Q.empty()){ 
        cot++;
        coord u=Q.front();
        int nx=u.x,ny=u.y;
        Q.pop();
        vis[nx][ny]=false;
        for(int k=0;k<4;++k){
            int ux=nx+walk[k][0],uy=ny+walk[k][1];
            if(ux<1||uy<1||ux>N||uy>N||matrix[ux][uy]!=0||vis[ux][uy]==false)   continue;
            Q.push(coord{ux,uy});
        }
    }
    solve();
    return 0;
}

by Misaki_Wang @ 2022-07-06 21:10:32

稍微解释下，思路是第一个'1'左下方必定是0，以这个0开始对封闭区域内的0进行染色，但是第5个点TLE过不去

by openallzzz @ 2022-07-14 17:39:47

@WBYZ 第一个'1'左下方必定是0这句话不是对的，比如， 000 010 101 010

换一种思路吧

by openallzzz @ 2022-07-14 17:43:28

有一种思路比较好理解，是这样的，对于矩形的边界上的0，一定不属于1包围的圈，因为这些点至少会有一个方向不存在1（至少是因为边界上的点的四周至少有一个方向的点是不合法的，不合法的点固然不存在1）

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 35;

int n;
int g[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x, int y, int c)
{
    g[x][y] = c;
    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i], t = (c == 2 ? 0 : 2);
        if(a >= 1 && a <= n && b >= 1 && b <= n && g[a][b] == t)
            dfs(a, b, c);
    }
}

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

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(g[i][j] == 0)
                dfs(i, j, 2);

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(i == 1 || i == n || j == 1 || j == n)
                if(g[i][j] == 2)
                    dfs(i, j, 0);

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
            printf("%d ", g[i][j]);
        puts("");
    }
    return 0;
}