FZU1205/SDUT1157_小鼠迷宫问题(DFS+BFS)

本文主要是介绍FZU1205/SDUT1157_小鼠迷宫问题(DFS+BFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解题报告

http://blog.csdn.net/juncoder/article/details/38146041

题目传送门

题意

求最短路和最短路的路数。

思路：

BFS+DFS，先求出最短路。在DFS搜等于最短路的条数。

不加优化SDUTOJ过了，数据就是水。

确定了最短路的长度，加上奇偶剪枝FOJ也过了。

#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int mmap[1000][1000],vis[1000][1000],n,m,k,cnt,q,p,r,minstep,s;
struct node {int x,y,step;
};
int dx[]= {-1,0,1,0};
int dy[]= {0,1,0,-1};
int bfs()
{queue<node>Q;node next,now;now.x=p;now.y=q;now.step=0;vis[p][q]=1;Q.push(now);while(!Q.empty()) {now=Q.front();Q.pop();if(now.x==r&&now.y==s) {return now.step;}for(int i=0; i<4; i++) {next.x=now.x+dx[i];next.y=now.y+dy[i];if(next.x>=1&&next.x<=n&&next.y>=1&&next.y<=m&&!mmap[next.x][next.y]&&!vis[next.x][next.y]) {next.step=now.step+1;Q.push(next);vis[next.x][next.y]=1;}}}
}
void dfs(int b,int e,int step)
{if(b==r&&e==s&&minstep==step) {cnt++;return ;}//if(step>minstep)return ;没优化if(abs(b-r)+abs(e-s)+step>minstep)return ;for(int i=0; i<4; i++) {int x=b+dx[i];int y=e+dy[i];if(x>=1&&x<=n&&y>=1&&y<=m&&!mmap[x][y]&&!vis[x][y]) {// printf("%d %d\n",x,y);vis[x][y]=1;dfs(x,y,step+1);vis[x][y]=0;}}
}
int main()
{int i,j,x,y;while(~scanf("%d%d%d",&n,&m,&k)) {cnt=0;memset(mmap,0,sizeof(mmap));memset(vis,0,sizeof(vis));for(i=0; i<k; i++) {scanf("%d%d",&x,&y);mmap[x][y]=1;}scanf("%d%d",&p,&q);scanf("%d%d",&r,&s);minstep=bfs();printf("%d\n",minstep);memset(vis,0,sizeof(vis));dfs(p,q,0);vis[p][q]=1;printf("%d\n",cnt);}
}

1205 小鼠迷宫问题

Accept: 535 Submit: 1729
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem 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)。(1≤p,r≤n; 1≤q,s≤m)

结果输出