求助dalao，测试点能过样例也对但是全RE

Editzed @ 2021-09-10 18:33:45

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int a[40][40];
int n;
bool f[40][40];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    queue<int> x;
    queue<int> y;
    x.push(0);
    y.push(0);
    while(!x.empty()){
        f[0][0]=1;
        for(int i=0;i<4;i++){
            int nx=x.front()+dx[i];
            int ny=y.front()+dy[i];
            if(nx>=0&&ny<=n+1&&ny>=0&&ny<=n+1&&a[nx][ny]==0&&f[nx][ny]==0){
                f[nx][ny]=1;
                x.push(nx);
                y.push(ny);
            }
        }
        x.pop();
        y.pop();
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]==0&&f[i][j]==0){
                cout<<2<<" ";
            }
            else cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

by dingshengyang @ 2021-09-10 18:37:48

我的：

#include<bits/stdc++.h>
using namespace std;
int n;
char maps[31][31] ;
int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}},vis[31][31];
struct node{
    int x,y;
}s;
void bfs(int x,int y){
    s.x = x;
    s.y = y;
    queue <node> que ;
    que.push(s);
    vis[x][y] = 1;
    while(!que.empty()){
        node now = que.front ();
        que.pop();
        for(int i=0;i<4;i++){
            node next = now;
            next.x+=dir[i][0];
            next.y+=dir[i][1];
            if(maps[next.x][next.y] == '1' || vis[next.x][next.y] == 1) continue;
            else maps[next.x][next.y] = '2';
            vis[next.x][next.y] = 1;
            que.push(next);
        }
    }
}
int main(){
    cin >> n;
    memset (maps,'1',sizeof(maps));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>maps[i][j];
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=n;j++){
            if(maps[i][j] == '1') break;
            else vis[i][j] = 1 ;
        }
        for(int j=n;j>=1;j--){
            if(maps[i][j] == '1') break;
            else vis[i][j] = 1 ;
        }
    }
    for(int j=n;j>=1;j--){
        for(int i=1;i<=n;i++){
            if(maps[i][j] == '1') break;
            else vis[i][j] = 1 ;
        }
        for(int i=n;i>=1;i--){
            if(maps[i][j] == '1') break;
            else vis[i][j] = 1 ;
        }
    }
    int x=1,y=1,t=1;
    for(int i=1;i<=n && t;i++){
        for(int j = 1;j<=n && t;j++){
            if(vis[i][j] == 0 && maps[i][j] == '0') {
                x = i,y = j;
                t = 0;
            }
        }
    }
    maps[x][y] = '2';
    bfs(x,y);
    for(int i = 1;i<=n;i++){
        cout << maps[i][1];
        for(int j = 2;j<=n;j++){
            cout << " " <<maps[i][j];
        }
        cout << endl;
    }
    return 0;
}

by Escapism @ 2021-09-10 18:42:39

大水法

DFS + 骚操作

#include <iostream>
#include <string>
using namespace std;

int a[600][600];

void dfs(int x,int y,int type){ //type代表将搜过的0标记的数字，搜外围就标2，防水空间就标1
    a[x][y] = type;
    if (a[x+1][y]!=0 && a[x-1][y]!=0 && a[x][y+1]!=0 && a[x][y-1]!=0){
        return;
    }
    if (a[x + 1][y] == 0)dfs(x + 1,y,type);
    if (a[x - 1][y] == 0)dfs(x - 1,y,type);
    if (a[x][y + 1] == 0)dfs(x,y + 1,type);
    if (a[x][y - 1] == 0)dfs(x,y - 1,type);
}
int main(){
    int n;
    cin>>n;
    for (int i = 0;i <= n + 1;i++){ //越界保护，将所有边界标为2
        for (int j = 0;j <= n + 1;j++){
            a[i][j] = 2;
        }
    }
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            cin>>a[i][j];
        }
    }
    // for (int i = 0;i <= n + 1;i++){
    //  for (int j = 0;j <= m + 1;j++) cout<<a[i][j];
    //  cout<<endl;
    // }
    int x = 2,y = 1;
    int side = 1;
    bool flag = false;
    while (true){ //边界搜索，将边界搜到的空地标为2（即淹水状态）
        if (flag == true && x == 1 && y == 1) break;
        if (a[x][y] == 0){
            dfs(x,y,2);
        }       
        if (x == n && y == 1) side = 2;
        if (x == n && y == n) side = 3;
        if (x == 1 && y == n) side = 4;
        if (side == 1) x++;
        if (side == 2) y++;
        if (side == 3) x--;
        if (side == 4) y--;
        flag = true;

    }
    for (int i = 0;i <= n;i++){
        for (int j = 0;j <= n;j++){ //保护区搜索，空地标为1（即围墙）
            if (a[i][j] == 0) dfs(i,j,3);
        }
    }
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            if (a[i][j] == 2) cout<<0<<" ";
            else if (a[i][j] == 3) cout<<2<<" ";
            else cout<<1<<" ";
        }
        cout<<endl;
    }

by thatsgame @ 2021-09-10 18:46:21

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=101;
int a[maxn][maxn];
int n;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
struct node
{
    int x;
    int y;
};
queue <node> lq;
bool vis[maxn][maxn];
void bfs(int x,int y)
{
    lq.push((node){x,y});
    vis[0][0]=1;
    while(!lq.empty())
    {
        for(int i=0;i<4;i++)
        {
            int xx=lq.front().x+dx[i];
            int yy=lq.front().y+dy[i];

            if(!vis[xx][yy]&&xx>=0&&xx<=n+1&&yy>=0&&yy<=n+1&&a[xx][yy]==0)
            {
                lq.push((node){xx,yy});
                vis[xx][yy]=1;
            }
        }
        lq.pop();
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    bfs(0,0);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]==0&&vis[i][j]==0)
            {
                cout<<2<<" ";
            }
            else cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

我的

by Editzed @ 2021-09-10 18:48:35

用深搜过了

by lamp_forever @ 2021-09-10 18:48:58

话说不用结构体可能更好点。。。

by lamp_forever @ 2021-09-10 18:49:35

#include<bits/stdc++.h>
using namespace std;
int xx[]={0,-1,0,1};
int yy[]={1,0,-1,0};
int mp[40][40];
bool vis[40][40];
int n,m;
queue<int>x;
queue<int>y;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    cin>>mp[i][j];
    x.push(0);
    y.push(0);
    vis[0][0]=1;
    while(!x.empty())
    {
        for(int i=0;i<4;i++)
        {
            int dx=x.front()+xx[i];
            int dy=y.front()+yy[i];
            if(dx>=0&&dx<=n+1&&dy>=0&&dy<=n+1&&mp[dx][dy]==0&&vis[dx][dy]==0)
            {
                x.push(dx);
                y.push(dy);
                vis[dx][dy]=1;
            }   
        }
        x.pop();
        y.pop();
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            if(mp[i][j]==0&&vis[i][j]==0)
                cout<<2<<" ";
            else
                cout<<mp[i][j]<<" ";
        cout<<endl; 
    }

}