首页 > 代码库 > SDUT1157:小鼠迷宫问题(bfs+dfs)
SDUT1157:小鼠迷宫问题(bfs+dfs)
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1157
题目描述
小鼠a与小鼠b身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿上，下，左，右4个方向进入未封闭的房间。小鼠a位于迷宫的(p，q)方格中，它必须找出一条通向小鼠b所在的(r，s)方格的路。请帮助小鼠a找出所有通向小鼠b的最短道路。
请编程对于给定的小鼠的迷宫，计算小鼠a通向小鼠b的所有最短道路。
请编程对于给定的小鼠的迷宫，计算小鼠a通向小鼠b的所有最短道路。
输入
本题有多组输入数据，你必须处理到EOF为止。
每组数据的第一行有3个正整数n，m，k，分别表示迷宫的行数，列数和封闭的房间数。
接下来的k行中，每行2个正整数，表示被封闭的房间所在的行号和列号。
最后的2行，每行也有2个正整数，分别表示小鼠a所处的方格(p，q)和小鼠b所处的方格(r，s)。
每组数据的第一行有3个正整数n，m，k，分别表示迷宫的行数，列数和封闭的房间数。
接下来的k行中，每行2个正整数，表示被封闭的房间所在的行号和列号。
最后的2行，每行也有2个正整数，分别表示小鼠a所处的方格(p，q)和小鼠b所处的方格(r，s)。
输出
对于每组数据，将计算出的小鼠a通向小鼠b的最短路长度和有多少条不同的最短路输出。
每组数据输出两行，第一行是最短路长度；第2行是不同的最短路数。
每组输出之间没有空行。
如果小鼠a无法通向小鼠b则输出“No Solution!”。
每组数据输出两行，第一行是最短路长度；第2行是不同的最短路数。
每组输出之间没有空行。
如果小鼠a无法通向小鼠b则输出“No Solution!”。
示例输入
8 8 33 34 56 62 17 7
示例输出
1196
题目大意：在一个迷宫内输出位置a到位置b的最短距离，以及一共有多少种不同的最短路径数。
分析：利用bfs可以计算出最短路径的距离，然后用dfs计算出等于有多少种不同的最短路径。
题目解析：
通过做这题，发现对算法的思想很渣渣，拿到题简直无法先手，有点弄混bfs与dfs，
bfs可以求最短路，但无法求最短路径的数目，但dfs 不同，它通过不断的回溯与查找，可以
遍历所有的情况。
#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <queue>using namespace std;char map[101][101];int v[101][101];struct node{ int ans,x,y;};struct node t,f;int a[2],b[2];int fx[]= {1,-1,0,0};int fy[]= {0,0,1,-1};int n,m,k,flag,sum;void bfs(){ queue<node>q; memset(v,0,sizeof(v)); t.x=a[0]; t.y=a[1]; t.ans=0; q.push(t); v[a[0]][a[1]]=1; while(!q.empty()) { t=q.front(); q.pop(); if(t.x==b[0]&&t.y==b[1]) { printf("%d\n",t.ans); flag=t.ans; return ; } for(int i=0; i<4; i++) { f.x=t.x+fx[i]; f.y=t.y+fy[i]; if(f.x>=1&&f.x<=n&&f.y>=1&&f.y<=m&&v[f.x][f.y]==0&&map[f.x][f.y]!=1) { f.ans=t.ans+1; v[f.x][f.y]=1; q.push(f); } } } printf("No Solution!\n"); return ;}void dfs(int xx,int yy,int ans){ int tx,ty; if(xx==b[0]&&yy==b[1]&&ans==flag) { sum++; } if(xx>b[0]||yy>b[1]||ans>=flag) return ; for(int i=0; i<4; i++) { tx=xx+fx[i]; ty=yy+fy[i]; if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&v[tx][ty]==0&&map[tx][ty]!=1&&ans<flag) { v[tx][ty]=1; dfs(tx,ty,ans+1); v[tx][ty]=0; } }}int main(){ int xx,yy; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { flag=0; sum=0; memset(map,0,sizeof(map)); for(int i=1; i<=k; i++) { scanf("%d%d",&xx,&yy); map[xx][yy]=1; } scanf("%d%d",&a[0],&a[1]); scanf("%d%d",&b[0],&b[1]); bfs(); if(flag==0) continue; memset(v,0,sizeof(v)); v[a[0]][a[1]]=0; dfs(a[0],a[1],0); printf("%d\n",sum); } return 0;}
SDUT1157:小鼠迷宫问题(bfs+dfs)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。