【计蒜客】走迷宫

╰+哭是因爲堅強的太久メ 2021-12-21 20:55 313阅读 0赞

## **总而言之，关于迷宫好像大部分都是搜索题....** ##

# **先看一下题：（数据范围好小啊** #

** **

**给一个n行m列的2维的迷宫，`'S'`表示迷宫的起点，`'T'`表示迷宫的终点，`'#'`表示不能通过的点，`'.'` 表示可以通过的点。你需要从`'S'`出发走到`'T'`，每次只能上下左右走动，并且只能进入能通过的点，每个点只能通过一次。现在要求你求出有多少种通过迷宫的的方案。**

### **输入格式** ###

**第一行输入 n, m(1≤n,m≤10)表示迷宫的大小**

**接下来输入n行字符串表示迷宫。**

### **输出格式** ###

**输入通过迷宫的方法数。**

#### **样例输入1** ####

2 3 S.# ..T

#### **样例输出1** ####

#### **样例输入2** ####

3 3 S.. .#.
    ..T

#### **样例输出2** ####

2
    
    思路： 这道题其实就是一道深搜的模板，找到起点，分四个方向进行搜索，然后进行判定，判定是否越界或已被vis 数组标记或根本不能走。直到找到终点为止，方案数加一，并返回。 大体过程：
     存char类型的图 -----> 进行dfs，寻找终点（注意特判），方案数累加 ------> 输出方案数
    
    
     下面是AC代码：

1 #include<cstdio>
     2 #include<iostream>
     3 
     4 using namespace std;
     5 
     6 
     7 const int maxn = 25;
     8 
     9 char g[maxn][maxn];
    10 bool vis[maxn][maxn];
    11 int cnt;//方案数 
    12 int qx, qy;//起点横纵坐标 
    13 int m, n;
    14 
    15 void dfs(int x, int y){
    16     if(g[x][y] == 'T'){
    17         cnt++;//找到终点，方案数+1 
    18         return;
    19     }
    20     int u, o;
    21     for(int i = 1; i <= 4; i++){
    22         //进行四个方向的搜索 
    23         if(i == 1) u = x, o = y - 1;
    24         else if(i == 2) u = x, o = y + 1;
    25         else if(i == 3) u = x + 1, o = y;
    26         else u = x - 1, o = y;
    27         if(u < 1 || o < 1 || o > m || u > n) continue;//越界 
    28         if(g[u][o] == '#') continue;//障碍 
    29         if(vis[u][o]) continue;//已被访问 
    30         vis[u][o] = 1;
    31         dfs(u, o);//再次进行 
    32         vis[u][o] = 0;
    33     }
    34 }
    35         
    36 
    37 
    38 int main(){
    39     scanf("%d%d", &n, &m);
    40     for(int i = 1; i <= n; i++){
    41         for(int j = 1; j <= m; j++){
    42             cin>>g[i][j];
    43             if(g[i][j] == 'S')  qx = i, qy = j;
    44         }
    45     }
    46     vis[qx][qy] = 1;
    47     dfs(qx, qy);//从起点开始 
    48     printf("%d\n", cnt);
    49     return 0;
    50 }

转载于:https://www.cnblogs.com/New-ljx/p/10574938.html