(bfs) acwing 844. Labyrinth

844. Labyrinth

Topic link https://www.acwing.com/problem/content/846/
subject ：

Ideas ：bfs

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
typedef struct Node{
    
    int x,y,ct;
}node;
int n,m;
bool vis[110][110];
int a[110][110];
int fx[4][2]={
    {
    1,0},{
    -1,0},{
    0,1},{
    0,-1}};
int res=10010;
node q[10010];
int  bfs(){
    
    int f=0,r=-1;
    q[++r]={
    1,1,0};
    while(f<=r){
    
        node temp=q[f++];
        if(temp.x==n&&temp.y==m){
    
            return temp.ct;
            break;
        }
        for(int i=0;i<4;i++){
    
            int xx=temp.x+fx[i][0],yy=temp.y+fx[i][1];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!a[xx][yy]&&!vis[xx][yy]){
    
                q[++r]={
    xx,yy,temp.ct+1};
                vis[xx][yy]=1;
            }
        }
    }
}
int main(){
    
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);

    cout<<bfs();
    return 0;
}

dfs+ prune , But I can't pass

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
int n,m;
bool vis[110][110];
int a[110][110];
int fx[4][2]={
    {
    1,0},{
    -1,0},{
    0,1},{
    0,-1}};
int res=10010;
void dfs(int x,int y,int ct){
    
    vis[x][y]=1;
    if(x==n&&y==m){
    
        res=min(res,ct);
        vis[x][y]=0;
        return ;
    }
    if(res<ct){
    
        vis[x][y]=0;
        return ;
    }
    for(int i=0;i<4;i++){
    
        int xx=x+fx[i][0],yy=y+fx[i][1];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!a[xx][yy]&&!vis[xx][yy]){
    
            dfs(xx,yy,ct+1);
        }
    }
    vis[x][y]=0;
}
int main(){
    
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    dfs(1,1,0);
    cout<<res;
    return 0;
}