题目链接：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!”。
如果小鼠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 ;
}