如果你32分

P1162 填涂颜色

dyh_120 @ 2024-08-21 22:39:10

可以看看图形外围一圈是不是都考虑了

for (int i=1;i<=n;i++){
        if (mp[i][n]==0) dfs(i,n);
        if (mp[i][1]==0) dfs(i,1);
        if (mp[1][i]==0) dfs(1,i);
        if (mp[n][i]==0) dfs(n,i);
    } 

然后再进行深搜


by cccckick @ 2024-11-28 22:37:52

请问一下图形外围一圈是不是都考虑了是啥意思呀


by Dino21 @ 2024-12-18 13:09:44

@dyh_120还是不对啊

#include<iostream>  
using namespace std;
int maze[114][114],ans=0,dx[8]={-1,1,0,0},dy[8]={0,0,-1,1},n,G[114][114];
void slove1(int x,int y){
    for(int d=0;d<4;d++)
    {
        int xx=x+dx[d],yy=y+dy[d];
        if(xx>=0&&xx<n&&yy>=0&&yy<n&&maze[xx][yy]==0)
        {
            G[xx][yy]=2;
            maze[xx][yy]=1;
            slove1(xx,yy);
        }
    }
}
void slove2(int x,int y){
    for(int d=0;d<4;d++)
    {
        int xx=x+dx[d],yy=y+dy[d];
        if(xx>=0&&xx<n&&yy>=0&&yy<n&&G[xx][yy]==2)
        {
            G[xx][yy]=0;
            slove2(xx,yy);
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&maze[i][j]);
            G[i][j]=maze[i][j];
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(maze[i][j]==0)
            {
                maze[i][j]=1;
                G[i][j]=2; 
                slove1(i,j);
                ans++;
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        if(G[i][n-1]==0)slove2(i,n-1);
        if(G[i][0]==0)slove2(i,0);
        if(G[0][i]==0)slove2(0,i);
        if(G[n-1][i]==0)slove2(n-1,i);
    }
    slove2(0,0);
    slove2(0,n-1);
    slove2(n-1,n-1);
    slove2(n-1,0);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            printf("%d ",G[i][j]);
        }
        printf("\n");
    }
    return 0;
}

by dyh_120 @ 2024-12-21 19:52:29

@Dino21

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

const int N=35;
int n,mp[N][N];
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

bool check(int x,int y){
    return x>0 && x<=n && y>0 && y<=n && mp[x][y]==0;
}

void dfs(int x,int y){
    if (mp[x][y]==1) return;
    for (int i=0;i<=4;i++){
        int dx=x+dir[i][0];
        int dy=y+dir[i][1];
        if (check(dx,dy)){
            mp[dx][dy]=-1;
            dfs(dx,dy);
        }

    }
}

int main (){
    cin >> n;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            cin >> mp[i][j]; 
    for (int i=1;i<=n;i++){
        if (mp[i][n]==0) dfs(i,n);
        if (mp[i][1]==0) dfs(i,1);
        if (mp[1][i]==0) dfs(1,i);
        if (mp[n][i]==0) dfs(n,i);
    } 
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            if (mp[i][j]==-1)
                cout << 0 << " ";
            else if (mp[i][j]==1)
                cout << 1 << " ";
            else cout << 2 << " ";
        }
        cout << endl;
    }
    return 0;
}

|