[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

11 96

 

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

 

代码如下：

 #include <iostream>
 #include <queue>
 #include <cstring>
 #define maxn 101
 using namespace std;
 typedef long long LL;
 struct node{
     int sx, sy;
     node(int x, int y) :sx(x), sy(y){};
     node(){};
 };
 int n, m, k, mpt[maxn][maxn], vis[maxn][maxn], dis[][] = { , , -, , , -, ,  };
 LL dp[maxn][maxn];
 //dp[i][j]代表路径条数,mpt[i][j]最短路程的值
 int BFS(int sx, int sy, int ex, int ey){
     dp[sx][sy] = ;//初始情况1条路径
     vis[sx][sy] = ;
     node start(sx, sy);
     queue<node>Q;
     Q.push(start);
     while (!Q.empty()){
         node now = Q.front();
         Q.pop();
         if (now.sx == ex && now.sy == ey)//找到终点，返回最短路径
             return mpt[now.sx][now.sy];
         for (int i = ; i < ; i++){
             int x = now.sx + dis[i][];
             int y = now.sy + dis[i][];
             if (x >=  && x <= n && y >=  && y <= m && mpt[x][y] != -){
                 if (!vis[x][y]){
                     vis[x][y] = ;
                     mpt[x][y] = mpt[now.sx][now.sy] + ;//最短路程加1
                     dp[x][y] = dp[now.sx][now.sy];//直接赋值
                     node next(x, y);
                     Q.push(next);
                 }
                 else
                     dp[x][y] += dp[now.sx][now.sy];
             }
         }
     }
     return -;
 }
 int main(){
     int x, y, sx, sy, ex, ey;
     while (cin >> n >> m >> k){
         memset(mpt, , sizeof(mpt));
         memset(dp, , sizeof(dp));
         memset(vis, , sizeof(vis));
         for (int i = ; i < k; i++){
             cin >> x >> y;
             mpt[x][y] = -;//标记为障碍物
         }
         cin >> sx >> sy >> ex >> ey;
         int ans = BFS(sx, sy, ex, ey);
         if (ans == -)
             cout << "No Solution!" << endl;
         else
             cout << mpt[ex][ey] << endl << dp[ex][ey] << endl;
     }
     return ;
 }