全TLE求助

B3625 迷宫寻路

zyh0413 @ 2024-03-23 09:32:02

测试点全是TLE,不会调,求大佬帮忙:

#include<bits/stdc++.h>
using namespace std;
int n,m;
char c[105][105];
bool dfs(int x,int y,int t){
    if(x==n && y==m)
    {
        return true;
    }
    if(t==m*n)
    {
        return false;
    }
    bool a[4];
    if(c[x+1][y]=='.')
    {
        a[1]=dfs(x+1,y,t+1);
    }
    if(c[x-1][y]=='.' && x!=1)
    {
        a[2]=dfs(x-1,y,t+1);
    }
    if(c[x][y+1]=='.')
    {
        a[3]=dfs(x,y+1,t+1);
    }
    if(c[x][y-1]=='.' && y!=1)
    {
        a[4]=dfs(x,y-1,t+1);
    }
    return a[1]||a[2]||a[3]||a[4];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>c[i][j];
        }
    }
    if(dfs(1,1,0))
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }
    return 0;
}

by SparkingDaydream @ 2024-05-15 21:08:16

我也tle了几发,事实上这道题用迷宫找路的方法去做,回溯的过程肯定会TLE的,不如用连通图的思路去想,从(1,1)开始求连通图,看最后一个点是不是(n,m)如果是,则(1,1)与(n,m)连通,就可以判定yes了


|