5 和3 WA

songsonghui @ 2022-03-03 17:42:14

#include <iostream>
#include <cstring>
int n;
int map[35][35];
int mark[35][35];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

void dfs(int x,int y){
    if(map[x][y]==1||x<0||x>n+1||y<0||y>n+1||mark[x][y]==1) return;
    mark[x][y] = 1;//标记已经走过 
    for(int i =0;i<4;i++){//4个方向移动 
        if(y+dy[i]>n) dfs(x+1,1);//到了右边缘 
        else dfs(x+dx[i],y+dy[i]);
    }
}
int main(int argc, char** argv) {
    memset(mark,0,sizeof(mark));
    memset(map,0,sizeof(map));
    scanf("%d",&n);
    for(int i= 1;i<=n;i++){//输入 
        for(int j=1;j<=n;j++)
        scanf("%d",&map[i][j]);
    }
    dfs(0,0);

    for(int i =1;i<=n;i++){
        for(int j =1;j<=n;j++){
            if(mark[i][j]==0&&map[i][j]==0) map[i][j] = 2;
            //mark里标记为0则为内圈，内圈中为0的改为2
        }
    }
    for(int i =1;i<=n;i++){//输出 
        for(int j =1;j<=n;j++) printf("%d ",map[i][j]);
        printf("\n");
    }
    return 0;
}

by WangYinxiAlex @ 2023-07-31 14:47:25

@songsonghui

发点自己的想法：

#include<iostream>
using namespace std;
int a[31][31];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cin>>a[i][j];
    }
    for(int i=2;i<n;i++){
        for(int j=2;j<n;j++){
            if(a[i][j]!=1)a[i][j]=2;
        }
    }
    for(int i=2;i<n;i++){
        for(int j=2;j<n;j++){
            if(a[i][j]!=1&&\
            (a[i-1][j]==0||a[i][j-1]==0||a[i+1][j]==0||a[i][j+1]==0)){
                a[i][j]=0;
            }
        }
    }
    for(int i=n-1;i>1;i--){
        for(int j=n-1;j>1;j--){
            if(a[i][j]!=1&&\
            (a[i-1][j]==0||a[i][j-1]==0||a[i+1][j]==0||a[i][j+1]==0)){
                a[i][j]=0;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cout<<a[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

注释：

10-14行：由于最多矩形的边缘也是在最外面一周，所以最外面的0肯定都不是矩阵内的。
15-23行：从左、上方向判断这个点四周是不是有矩形外的点（0），如果有，说明这个点也不是矩形内的。
24-32行：但只从左、上方向看是不够的（如图1，这个是左、上方向的漏洞），还得从右、下方向判断。
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 0 1 1 1 1 0 1
1 0 1 0 0 1 1 1
1 0 1 0 0 0 0 0
1 0 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1
图1
（第3行第2列、第3行第3列、第4行第2列、第4行第3列、第4行第4列均无法被赋值）

按照这个办法，可以AC。

如果AC了，别忘了关注哦~