大犇(ba)们，救救孩子吧(玄关)

B3625 迷宫寻路

_Dayao_ @ 2024-12-14 17:12:46

救救我

怎么就TLE(已红温)

#include<bits/stdc++.h>
using namespace std;
int n,m,sum=0;
bool b[1001][1001]={0},c=0;
char a[1001][1001];
void dfs(int x,int y){
    if(a[x][y]=='#')return;
    if(x==n&&y==m&&c==0){
        c=1;
        return;
    }
    if(b[x+1][y]==0&&a[x+1][y]=='.'){
        b[x][y]=1;
        dfs(x+1,y);
        b[x][y]=0;
    }
    if(b[x-1][y]==0&&a[x-1][y]=='.'){
        b[x][y]=1;
        dfs(x-1,y);
        b[x][y]=0;
    }
    if(b[x][y-1]==0&&a[x][y-1]=='.'){
        b[x][y]=1;
        dfs(x,y-1);
        b[x][y]=0;
    }
    if(b[x][y+1]==0&&a[x][y+1]=='.'){
        b[x][y]=1;
        dfs(x,y+1);
        b[x][y]=0;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>a[i][j];
    }
    dfs(1,1);
    if(!c)cout<<"No";
  if(c)cout<<"Yes";
}

by weiyuchen4510 @ 2024-12-20 21:01:27

@Dayao

这题用回溯真的是天才

#include<iostream>
using namespace std;
int n,m,b[110][110],c;
char a[110][110];
void dfs(int x,int y)
{
    if(x>n||y>m||x<1||y<1||a[x][y]=='#'||b[x][y]||c) return;
    if(x==n&&y==m)
    {
        cout<<"Yes";
        c=1;
        return;
    }
    b[x][y]=1;
    dfs(x+1,y);
    dfs(x-1,y);
    dfs(x,y+1);
    dfs(x,y-1);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    dfs(1,1);
    if(!c) cout<<"No";
    return 0;
}

上一页 |