844. 走迷宫

应该用bfs，dfs也可以但是会TLE

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int N=110;
int mp[N][N];
int d[N][N];
int n,m;
typedef pair<int,int> PII;

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int step=0;
int minstep=1000;

int bfs(){
    memset(d,0,sizeof(d));
    d[1][1]=0;
    queue<PII>q;
    q.push({1,1});
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        int x=t.first,y=t.second;
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a>=1 && a<=n && b>=1 && b<=m && mp[a][b]==0 ){
                mp[a][b]=1;
                q.push({a,b});
                d[a][b]=d[x][y]+1;
            }
        }
    }
    return d[n][m];
    
}


int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&mp[i][j]);
        }
    }
    
    cout<<bfs();
    
    return 0;
}

这样写dfs为啥不行

这两种情况搜出来的路径长度是一样的，但是会重复搜，导致TLE

#include<iostream>
#include<cstring>
using namespace std;

const int N=110;
int mp[N][N],d[N][N];
int n,m;

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int step=0;
int minstep=1000;

void dfs(int x,int y){
    
    if(x==n&&y==m){
        return ;
    }
    mp[x][y]=1;
    for(int i=0;i<4;i++){
        int a=x+dx[i],b=y+dy[i];
        if(a>=1 && a<=n && b>=1 && b<=n && mp[a][b]==0){
            step++;
            if(step<d[a][b]){
                d[a][b]=step;
                dfs(a,b);
            }
            step--;
            mp[a][b]=0;
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&mp[i][j]);
        }
    }
    memset(d,0x7f,sizeof(d));
    dfs(1,1);
    cout<<d[n][m];
    
    return 0;
}