小鼠迷宫问题
问题描述
小鼠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)。(1≤p,r≤n; 1≤q,s≤m)
结果输出
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
这道题求最短路径和最短路径的条数。思路是先用bfs求出最短路径，然后dfs求出最短路径的条数，但是如果搜索两遍迷宫的话，就会超时，所以dfs搜索时应该注意，不要去搜迷宫了，而是直接搜步数。具体方法就是建立一个步数数组step[][]，在bfs里把他填好，然后dfs（step[][]） 这样可以省下很多时间。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;
typedef struct zuobiao{
int x,y;
int s;
}zb;
queue<zb> qq;
int n,m,k,p,q,r,s;
int a[100][110];
int step[100][110];
int anscnt;
int next[4][2] = {0,1,-1,0,0,-1,1,0};
void bfs(){
zb tmp;
tmp.x = p;
tmp.y = q;
tmp.s = 0;
step[p][q] = 0;
qq.push(tmp);
while(!qq.empty()){
for(int i = 0; i < 4; ++i){
int tx = next[i][0] + qq.front().x;
int ty = next[i][1] + qq.front().y;
if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
if(a[tx][ty] == 0 && step[tx][ty] == -1){
tmp.x = tx;
tmp.y = ty;
tmp.s = qq.front().s+1;
step[tx][ty] = tmp.s;
qq.push(tmp);
}
}
qq.pop();
}
}
void dfs(int x, int y){
if(x == p && y == q){
anscnt++;
return;
}
for(int i = 0; i < 4; ++i){
int tx = next[i][0] + x;
int ty = next[i][1] + y;
if(step[tx][ty] == step[x][y]-1){
dfs(tx,ty);
}
}
return;
}
void clearqq(){
while(!qq.empty()) qq.pop();
}
int main(int argc, char *argv[]) {
while(~scanf("%d%d%d",&n,&m,&k)){
clearqq();
anscnt = 0;
memset(a,0,sizeof(a));
memset(step,-1,sizeof(step));
for(int i = 1;i <= k; ++i){
int x,y;
scanf("%d%d",&x,&y);
a[x][y] = -1;
}
scanf("%d%d",&p,&q);
scanf("%d%d",&r,&s);
bfs();
if(step[r][s] == -1){
printf("No Solution!n");
continue;
}
dfs(r,s);
printf("%dn%dn",step[r][s],anscnt);
}
return 0;
}
相关知识
氟西汀耐药 cF1ko 小鼠中血清素预测的快速重组和对 5
养小鼠你要知道的那些事（三）：基因工程小鼠繁育方案
小鼠淋巴细胞玫瑰花结形成实验方法研究
不思议迷宫出云岛阵容推荐 不思议迷宫出云岛怎么打
国家遗传工程小鼠资源库项目在南京通过验收
不思议迷宫复活节彩蛋在哪 2019复活节活动彩蛋攻略
植物墙打造的绿色迷宫，看视频更精彩！
图为某转基因小鼠培育过程示意图.①
第一节 基因控制生物的性状练习题/试题及答案
Nature：免疫疗法阻断瘢痕形成，改善心力衰竭小鼠的心脏功能
网址: 小鼠迷宫问题 https://m.huajiangbk.com/newsview547011.html
| 上一篇: 什么是花呗 |
下一篇: 已知1花西币=79元，盘点各国留 |
