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);}
}

这篇关于FZU1205/SDUT1157_小鼠迷宫问题(DFS+BFS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---