小鼠迷宫问题
Time Limit: 2 Sec Memory Limit: 64 MB
Submit: 1 Solved: 1
[Submit][Status][Web Board]
Description
小鼠a与小鼠b身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿上，下，左，右4个方向进入未封闭的房间。小鼠a位于迷宫的(p，q)方格中，它必须找出一条通向小鼠b所在的(r，s)方格的路。请帮助小鼠a找出所有通向小鼠b的最短道路。
请编程对于给定的小鼠的迷宫，计算小鼠a通向小鼠b的所有最短道路。
Input
本题有多组输入数据，你必须处理到EOF为止。 每组数据的第一行有3个正整数n，m，k，分别表示迷宫的行数，列数和封闭的房间数。接下来的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
这是道搜索题，要求输出矩阵内a到b点的最短路长度，以及最短路的条数，并且要绕过限定的“封闭房间”，即某些格子无法走。
还可参照 ytu 2463:给小鼠补充代码 同样的题，不同的考察形式。
#include <iostream>
#include <cstring>
using namespace std;
int f[][];
int ax,ay;
int bx,by;
int dx[]={,,,-};
int dy[]={,,-,};
int _count=;
int _min=;
int n,m,k; void dfs(int d,int t,int curx,int cury)
{
if(t>_min)
return ;
if(curx< || cury< || curx>n- || cury>m-)
return ;
if(cury==by && curx==bx){
if(t<_min){
_count=;
_min=t;
}
else{
_count++;
}
return ;
}
for(int i=;i<;i++){
if(curx+dx[i]< || cury+dy[i]<) continue;
if(!f[curx+dx[i]][cury+dy[i]]){
f[curx+dx[i]][cury+dy[i]]=true;
dfs(i,t+,curx+dx[i],cury+dy[i]);
f[curx+dx[i]][cury+dy[i]]=false;
}
} return ;
} int main()
{
while(cin>>n>>m>>k){
_count=;
_min=;
memset(f,,sizeof(f));
for(int i=;i<=k;i++){
int a,b;
cin>>a>>b;
f[a][b]=true;
}
cin>>ax>>ay;
cin>>bx>>by;
dfs(-,,ax,ay);
cout<<_min<<endl;
cout<<_count<<endl;
}
return ;
}
Freecode : www.cnblogs.com/yym2013