题目描述

小明某天不小心进入了一个迷宫（如上图所示），请帮他计算走出迷宫的最少时间。规定每走一格需要一个单位时间，如果不能走到出口，则输出impossible。每次走只能是上、下、左、右4个方向之一。

输入格式:
测试数据有多组，处理到文件尾。每组测试数据首先输入2个整数n,m(0<n，m≤100)，代表迷宫的高和宽，然后n行，每行m个字符，各字符的含义如下：
S 代表小明现在所在的位置；T 代表迷宫的出口；# 代表墙，不能走；. 代表路，可以走。

输出格式:
对于每组测试，输出走出迷宫的最少时间，若不能走出则输出impossible。

输入样例:
4 4
S…

..

..#.
…T
4 4
S…

..

..#.
..#T
3 4
.S#.
.##.
…T
输出样例:
6
impossible
6
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB

样例

4 4
S...
#..#
..#.
...T
4 4
S...
#..#
..#.
..#T
3 4
.S#.
.##.
...T

6
impossible
6

算法1

(深搜) $O(nm)$

深搜

时间复杂度

$O(nm)$

参考文献

无

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,sx,sy,ex,ey,Min;
char ditu[105][105];
bool used[105][105];
int dx[]={0,-1,1,0,0};
int dy[]={0,0,0,-1,1};
void dfs(int x,int y,int s)
{
    if (x==ex&&y==ey)
        Min=min(Min,s); 
    else
    {
        for (int i=1;i<=4;i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx<1 || nx>n || ny<1 || ny>m)
               continue;
            if (ditu[nx][ny]!='#' && used[nx][ny]!=1)
            {
                used[nx][ny] = 1;
                dfs(nx,ny,s+1);
                used[nx][ny] = 0;
            } 
        }
    }
}
int main()
{
    while(cin>>n>>m)
    {
        Min=INT_MAX;
        memset(used,0,sizeof used);
        cnt=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                cin>>ditu[i][j];
                if(ditu[i][j]=='S') sx=i,sy=j;
                if(ditu[i][j]=='T') ex=i,ey=j;
            }
        used[sx][sy]=1; 
        dfs(sx,sy,0);
        if(Min==INT_MAX) cout<<"impossible\n";
        else cout<<Min<<"\n";
    }
}