题目描述

小明某天不小心进入了一个迷宫（如上图所示），请帮他判断能否出走出迷宫，如果可能，则输出一共有多少种不同的走法（对于某种特定的走法，必须保证不能多次走到同一个位置）。如果不能走到出口，则输出impossible。每次走只能是上、下、左、右4个方向之一。

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

输出格式:
对于每组测试，输出一共有多少种不同的走法，若不能走出则输出impossible。
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB

样例

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

4
impossible
1

算法

(深搜) $O(nm)$

简单深搜题

时间复杂度

$O(nm)$

参考文献

掌握深搜

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,sx,sy,ex,ey;
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)
{
    if (x==ex&&y==ey)
        cnt++;
    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);
                used[nx][ny] = 0;
            } 
        }
    }
}
int main()
{
    while(cin>>n>>m)
    {
        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);
        if(cnt==0) cout<<"impossible\n";
        else cout<<cnt<<"\n";
    }
}