TLE！！！

Libingyue2011 @ 2023-01-16 22:37:13

#include<bits/stdc++.h>//专属只有一块围住的 
using namespace std;
int a[45][45],n,x,y;
struct node{//二元组 node   (用 STL 的 pair 也行)
    int a,b;
};
bool turn(int x,int y){
    return (x<=n && y<=n && x>0 && y>0);
}
void read(){
    int num=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
            if(turn(i-1,j) && turn(i,j-1) && !num){
                if(a[i-1][j]==1 && a[i][j-1]==1 && a[i][j]==0){
                    x=i,y=j;
                    num++;
                }
            }
        }
    }
}
void bfs(int x,int y){
    queue<node>q;
    q.push((node){x,y});
    while(!q.empty()){
        int x2=q.front().a,y2=q.front().b;
        a[x2][y2]=2;
        q.pop();
        if(turn(x2+1,y2) && a[x2+1][y2]==0){
            q.push((node){x2+1,y2});
        }
        if(turn(x2-1,y2) && a[x2-1][y2]==0){
            q.push((node){x2-1,y2});
        }
        if(turn(x2,y2+1) && a[x2][y2+1]==0){
            q.push((node){x2,y2+1});
        }
        if(turn(x2,y2-1) && a[x2][y2-1]==0){
            q.push((node){x2,y2-1});
        }
    }
    return;
}
void print(){
//  cout<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
}
int main() {
    cin>>n;
    read();
    bfs(x,y);
    print();
    return 0;
}

by WangYinxiAlex @ 2023-07-31 14:41:24

@Libingyue2011 发点自己的想法：

#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了，别忘了关注哦~

by Libingyue2011 @ 2023-07-31 14:42:15

Thanks,but 我早就 AC 了。

by Libingyue2011 @ 2023-07-31 14:43:16

@WangYinxiAlex

by WangYinxiAlex @ 2023-07-31 14:46:09

oh···