第五个caseTLE了求助

P1162 填涂颜色

nob_lz @ 2024-10-21 19:20:51

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

int n;
int a[50][50];
bool vis[50][50];
int dy[50];

bool edge(int x,int y){
    if(x<0 || x>=n || y<0 || y>=n) return false;
    return true;
}

void cut(){
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
                if(a[i][j]==1) dy[i]++;       
            }
        }
    }

bool dfs(int x,int y){
    if(!edge(x,y))
        return false;
    if(a[x][y]==1) return true;
    if(vis[x][y]) return true;
    vis[x][y]=true;

    if(dfs(x+1,y) && dfs(x-1,y) && dfs(x,y+1) && dfs(x,y-1)){
        vis[x][y]=false;
        return true;
    }
    else{
       vis[x][y]=false;
       return false;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j) 
            cin>>a[i][j];
    }
    cut();
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            if(dy[i]>=2 && a[i][j]==0 && j!=0 && i!=0 && j!=n-1 && i!=n-1 && dfs(i,j) ) cout<<2<<' ';
            else 
            cout<<a[i][j]<<' ';
        }
       cout<<endl;
    }

    return 0;
}

我的思路是: 将符合情况的坐标进行dfs搜索,如果搜索到四个方向全是墙壁的话,就返回true, 不知道为啥第五个案例TLE了是不是因为什么没有剪枝叶什么的导致的 还是我的代码本身有问题?求助!!


by 违规用户名1053866 @ 2024-11-05 18:42:27

@nob_lz 这是个广搜,深搜比广搜慢(会超时)


by nob_lz @ 2024-11-06 13:11:45

@kkksc20 我想问一下,怎么判断出什么时候要用广搜什么时候深搜啊,特征是什么


by Jasenn @ 2024-11-12 02:04:34

你看看我的python代码,不会超时

全代码:

graph = []
n = int(input())
for i in range(n):
    graph.append(list(input().split()))

vis = [[0 for i in range(n)]for i in range(n)]
res = []

def fillin(x,y):
    if graph[x][y] == '0' and (x == 0 or x == n-1 or y == 0 or y == n-1):
        vis[x][y] = 1
        return False
    if graph[x][y] == '1' or vis[x][y]:
        return True
    vis[x][y] = 1
    res.append([x,y])
    a,b,c,d = fillin(x-1,y),fillin(x+1,y), fillin(x,y-1), fillin(x,y+1)
    return a and b and c and d
for x in range(n):
    for y in range(n):
        if graph[x][y] == '0' and not vis[x][y] and fillin(x,y):
            for p in res:
                graph[p[0]][p[1]] = '2'
        res = []
for l in graph:
    print(' '.join(l))

a,b,c,d = fillin(x-1,y),fillin(x+1,y), fillin(x,y-1), fillin(x,y+1) return a and b and c and d 这里很关键,不能因为发现边缘0点而立即返回否,要将所有0点都标记后,再返回否


|