[Swust OJ 409]--小鼠迷宫问题(BFS+记忆化搜索)

题目链接：http://acm.swust.edu.cn/problem/409/

Time limit(ms): 1000　　　　　　　　Memory limit(kb): 65535

Description

小鼠a与小鼠b身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿上，下，左，右4个方向进入未封闭的房间。小鼠a位于迷宫的(p，q)方格中，它必须找出一条通向小鼠b所在的(r，s)方格的路。请帮助小鼠a找出所有通向小鼠b的最短道路。

编程任务：
对于给定的小鼠的迷宫，编程计算小鼠a通向小鼠b的所有最短道路。

Input

第一行有3个正整数n，m，k，分别表示迷宫的行数，列数和封闭的房间数,1 < n,m < 100。接下来的k行中，每行2个正整数，表示被封闭的房间所在的行号和列号。最后的2行，每行也有2个正整数，分别表示小鼠a所处的方格(p，q)和小鼠b所处的方格(r，s)。

Output

将计算出的小鼠a通向小鼠b的最短路长度和有多少条不同的最短路输出。第一行是最短路长度。第2行是不同的最短路数。
如果小鼠a无法通向小鼠b则输出“No Solution!”。

Sample Input

8 8 3

3 3

4 5

6 6

2 1

7 7

Sample Output

解题思路：在最短路径的基础上还要求路径条数，那么自然而然的想到了记忆化搜索Orz~~~

代码如下：

 1 #include <iostream>
 2 #include <queue>
 3 #include <cstring>
 4 #define maxn 101
 5 using namespace std;
 6 typedef long long LL;
 7 struct node{
 8     int sx, sy;
 9     node(int x, int y) :sx(x), sy(y){};
10     node(){};
11 };
12 int n, m, k, mpt[maxn][maxn], vis[maxn][maxn], dis[4][2] = { 1, 0, -1, 0, 0, -1, 0, 1 };
13 LL dp[maxn][maxn];
14 //dp[i][j]代表路径条数,mpt[i][j]最短路程的值
15 int BFS(int sx, int sy, int ex, int ey){
16     dp[sx][sy] = 1;//初始情况1条路径
17     vis[sx][sy] = 1;
18     node start(sx, sy);
19     queue<node>Q;
20     Q.push(start);
21     while (!Q.empty()){
22         node now = Q.front();
23         Q.pop();
24         if (now.sx == ex && now.sy == ey)//找到终点，返回最短路径
25             return mpt[now.sx][now.sy];
26         for (int i = 0; i < 4; i++){
27             int x = now.sx + dis[i][0];
28             int y = now.sy + dis[i][1];
29             if (x >= 1 && x <= n && y >= 1 && y <= m && mpt[x][y] != -1){
30                 if (!vis[x][y]){
31                     vis[x][y] = 1;
32                     mpt[x][y] = mpt[now.sx][now.sy] + 1;//最短路程加1
33                     dp[x][y] = dp[now.sx][now.sy];//直接赋值
34                     node next(x, y);
35                     Q.push(next);
36                 }
37                 else
38                     dp[x][y] += dp[now.sx][now.sy];
39             }
40         }
41     }
42     return -1;
43 }
44 int main(){
45     int x, y, sx, sy, ex, ey;
46     while (cin >> n >> m >> k){
47         memset(mpt, 0, sizeof(mpt));
48         memset(dp, 0, sizeof(dp));
49         memset(vis, 0, sizeof(vis));
50         for (int i = 0; i < k; i++){
51             cin >> x >> y;
52             mpt[x][y] = -1;//标记为障碍物
53         }
54         cin >> sx >> sy >> ex >> ey;
55         int ans = BFS(sx, sy, ex, ey);
56         if (ans == -1)
57             cout << "No Solution!" << endl;
58         else
59             cout << mpt[ex][ey] << endl << dp[ex][ey] << endl;
60     }
61     return 0;
62 }

View Code