郑轻 1397 迷宫问题

标签：&& int 郑轻 迷宫 st ++ dx dy 1397

 

题目描述

ACM是一个喜欢玩游戏的小孩，他喜欢玩智力游戏，比如最近在玩走迷宫，这是一款超级耗费脑细胞的游戏。
和普通的走迷宫一样，游戏是一张迷宫图，其中有一些标记，'W'是墙，'.'是可走的路，起点在左上角，目标点在右下角。ACM从左上角出发，只能向下和向右走，游戏要你找出有多少种不同的走法。很有压力吧？那是对于非计算机专业的人来说！你怎么看？试试吧。

输入

首先输入一个整数T，表示接下来有T（0<T<=10）个测试实例。
每组测试实例第一行是两个整数n（0<n<=10）和m（0<m<=10），表示游戏是在一张n*m的迷宫图上进行，接下来是一个n*m的迷宫图。

输出

每组样例输出一个整数，表示ACM有多少种不同的走法。

样例输入 Copy

2
2 2
.w
.w
3 3
...
w..
...

样例输出 Copy

0
3

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 20, M = 20;
 5 
 6 int n, m;
 7 int cnt;
 8 char g[N][M];
 9 bool st[N][M];
10 
11 int depx[2] = {0, 1};
12 int depy[2] = {1, 0};
13 
14 void dfs(int x, int y) {
15     for (int i = 0; i < 2; i ++ ) {
16         int dx = x + depx[i], dy = y + depy[i];
17         if (dx < n && dx >= 0 && dy < m && dy >= 0 && !st[dx][dy] && g[dx][dy] == '.') {
18             st[dx][dy] = true;
19             if (dx == n - 1 && dy == m - 1) cnt ++ ;
20             dfs(dx, dy);
21             st[dx][dy] = false;
22         }
23     }
24     return ;
25 }
26 
27 int main() {
28     int t;
29     cin >> t;
30     while (t -- ) {
31         scanf("%d%d", &n, &m);
32         cnt = 0;
33         for (int i = 0 ; i < n; i ++ )
34             for (int j = 0; j < m; j ++ )
35                 scanf(" %c", &g[i][j]);
36         st[0][0] = true;
37         dfs(0, 0);
38         cout << cnt << endl;
39     }
40     return 0;
41 }

难度:最多两颗星, 熟练以后一颗星

 

标签：&&,int,郑轻,迷宫,st,++,dx,dy,1397
From： https://www.cnblogs.com/llihaotian666/p/17014602.html