dfs求调32pts玄关

dhlsgjr @ 2024-11-09 19:47:59

#include<bits/stdc++.h>
using namespace std;    
int mapp[35][35];int n;
int dx[]={0,0,0,1,-1},dy[]={0,1,-1,0,0};
void rs0(int x,int y)
{
    mapp[x][y]=-1;
    for(int i=1;i<=4;i++)
    {
        x+=dx[i],y+=dy[i];
        if(x<1||y<1||x>n||y>n)x-=dx[i],y-=dy[i];
        else if(mapp[x][y]==0||mapp[x][y]==2)
        {
            rs0(x,y);
            x-=dx[i],y-=dy[i];
        }
    }
}
void rs2(int x,int y)
{
    mapp[x][y]=2;
    for(int i=1;i<=4;i++)
    {
        x+=dx[i],y+=dy[i];
        if(x<1||y<1||x>n||y>n)x-=dx[i],y-=dy[i];
        else if(mapp[x][y]==0)
        {
            rs2(x,y);
            x-=dx[i],y-=dy[i];
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>mapp[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {

            if(i==1||j==1||j==n||i==n)
            {
                if(mapp[i][j]==0||mapp[i][j]==2)
                rs0(i,j);
            }
            else if(mapp[i][j]==0)
            {
                rs2(i,j);
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(mapp[i][j]==-1)mapp[i][j]=0;
            cout<<mapp[i][j]<<" ";
        }
        cout<<endl;
    }
}

by coool @ 2024-11-14 10:56:32

#include <bits/stdc++.h>
using namespace std;

int n,xi,yi;

int a[35][35],b[35][35];
int vis[35][35];

int fx[5] = {0,0,0,1,-1};
int fy[5] = {0,1,-1,0,0};

bool check1(int x, int y){
    if (x < 0 || y < 0 || x > n + 1 || y > n + 1 || a[x][y] == 1 || vis[x][y]) return false;
    else return true;
}
bool check2(int x, int y){
    if (x <= 0 || y <= 0 || x > n || y > n  || b[x][y] == 1 || vis[x][y]) return false;
    else return true;
}
void init(int x, int y){
    for (int i = 0; i < 5;i++){
        int xx = x + fx[i];
        int yy = y + fy[i];
        if (check1(xx,yy)){
            vis[x][y] = 1;
            a[xx][yy] = 9; // visted            
            init(xx,yy);
        }
    }   
}
void dfs(int x, int y){
    for (int i = 0; i < 5;i++){
        int xx = x + fx[i];
        int yy = y + fy[i];
        if (check2(xx,yy)){
            vis[x][y] = 1;
            b[xx][yy] = 2; // visted            
            dfs(xx,yy);
        }
    }   
}
int main(){
    cin >>n ;
    for (int i =1;  i<= n; i++){
        for (int j =1 ; j<=n;j++){
            cin >> a[i][j];
            b[i][j] = a[i][j];
        }
    }   
    init(0,0);
    for (int i =0;  i<= n+1; i++){
        for (int j =0 ; j<=n+1;j++){
            if (a[i][j] == 0){
                xi  =i;
                yi = j;
                break; 
            }
            if (xi && yi) break;
        }
    }
    memset(vis,0,sizeof(vis));
    dfs(xi,yi);
    for (int i =1;  i<= n; i++){
        for (int j =1 ; j<=n;j++){
            cout << b[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
} 

by h1yo @ 2024-11-20 15:54:01

我也用的dfs 可以参考一下

#include<iostream>

using namespace std;
const int N = 33;
int g[N][N];
int vis[N][N];
int n;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0};

void dfs(int x, int y) {
    if (g[x][y] == 1)return;
    if (g[x][y] == 0)vis[x][y]=1;
    for (int i = 1; i <= 3; i++) {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (tx<1 || tx>n || ty<1 || ty>n)continue;
        if (!vis[tx][ty])dfs(tx, ty);
    }
}

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 (i == 1 || j == 1 || i == n || j == n)dfs(i, j);
            else continue;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (vis[i][j] == 0 && g[i][j] == 0)g[i][j] = 2;
            cout << g[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}