wyh的迷宫

涉及知识点：求迷宫能否到达终点的，而不是求路径数的，用bfs时可以不用重置状态数组（回溯）。

题目描述

给你一个n*m的迷宫，这个迷宫中有以下几个标识：

s代表起点

t代表终点

x代表障碍物

.代表空地

现在你们涵哥想知道能不能从起点走到终点不碰到障碍物（只能上下左右进行移动，并且不能移动到已经移动过的点）。

输入描述:

输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，对于每一组测试数据，第一行输入2个数n和m(1<=n,m<=500)
接下来n行，每行m个字符代表这个迷宫，每个字符都是上面4个中的一种
数据保证只有一个起点和一个终点

输出描述:

对于每一组测试数据，如果可以的话输出YES，不可以的话输出NO

示例1

输入

复制1 3 5 s...x x...x ...tx

1
3 5
s...x
x...x
...tx

输出

复制YES

YES

想法：

用dfs求，结果超时了。毕竟都500层了……

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans;
char mg[510][510];
int a,b;//终点
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int st[510][510];
void dfs(int x,int y){
    for(int i=0;i<4;i++){
        int xx=dx[i]+x;
        int yy=dy[i]+y;
        if(xx<1||yy<1||xx>n||yy>m) continue;
        if(mg[xx][yy]=='x') continue;
        if(st[xx][yy]) continue;
        if(xx==a&&yy==b) {ans++; return;}
        st[xx][yy]=1;
        dfs(xx,yy);
        st[xx][yy]=0;
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){

        memset(st,0,sizeof(st));
        ans=0;
        cin>>n>>m;
        int x,y;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>mg[i][j];
                if(mg[i][j]=='s') { x=i,y=j;}
                if(mg[i][j]=='t') { a=i,b=j;}
            }
        }
        dfs(x,y);
        if(ans) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0 ;
}

想法：

今天看网课，讲到bfs的时间复杂度要比dfs小（其实是回溯了的dfs时间复杂度才比bfs大很多），所以就试试bfs的写法,过了。还学到了一个小技巧，队列中的坐标的存储可以不用数对pair，用一个数值表示。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans;
char mg[510][510];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int st[510][510];
queue <int> q;
void bfs(int x,int y){
    q.push(x*m+y);
    while(!q.empty()){
        int a=q.front()/m;
        int b=q.front()%m;
        q.pop();
        for(int i=0;i<4;i++){
            int xx=a+dx[i];
            int yy=b+dy[i];
            if(mg[xx][yy]=='x') continue;
            if(mg[xx][yy]=='t') { ans=1;break;}//到终点
            if(st[xx][yy]) continue;
            if(xx>=n||xx<0||yy<0||yy>=m) continue;
            st[xx][yy]=1;
            q.push(xx*m+yy);
        }
        if(ans==1) return ;
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        memset(st,0,sizeof(st));
        ans=0;
        cin>>n>>m;
        int x,y;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>mg[i][j];
                if(mg[i][j]=='s') { x=i,y=j;}
            }
        }
        st[x][y]=1;
        bfs(x,y);
        if(ans) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0 ;
}

事情到这并没有结束，我写完就去翻了一下别人的题解，发现其实也可以用dfs写出来，我们不需要具体路径，只需要知道起点终点是否连通（我本来想用连通块写的，但感觉还是会超时，就否决了），因此，本题不用回溯也不可以回溯，回溯会超时。这么做时间复杂度和上一个bfs的时一样的，就是全部格子都搜了一遍，时间复杂度为O（n*m）。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans;
char mg[510][510];
int a,b;//终点
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int st[510][510];
void dfs(int x,int y){
    for(int i=0;i<4;i++){
        int xx=dx[i]+x;
        int yy=dy[i]+y;
        if(xx<1||yy<1||xx>n||yy>m) continue;
        if(mg[xx][yy]=='x') continue;
        if(st[xx][yy]) continue;
        if(xx==a&&yy==b) {ans++; return;}
        st[xx][yy]=1;
        dfs(xx,yy);
        //st[xx][yy]=0;
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){

        memset(st,0,sizeof(st));
        ans=0;
        cin>>n>>m;
        int x,y;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>mg[i][j];
                if(mg[i][j]=='s') { x=i,y=j;}
                if(mg[i][j]=='t') { a=i,b=j;}
            }
        }
        dfs(x,y);
        if(ans) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0 ;
}

嗐，其实还是感觉怪怪的，再想想吧。