首页 > 代码库 > BFS [SWUST OJ 191] 迷宫逃离
BFS [SWUST OJ 191] 迷宫逃离
迷宫逃离(0191)
描述
江鸟突然想到了一个迷宫逃离的游戏，话说有三个人被困于一个n*m的迷宫里，他们三人都可以向上、向下、向左、向右四个方向进行走动，当然他们所在的初始位置没有障碍物，同时只能走到没有障碍物的格子上，现在江鸟要问你最少需要去掉多少个格子的障碍物，可以使他们三人之间两两互相可达。
输入
输入包括多组测试数据，每组测试数据第一行为两个整数n和m(2<=n,m<=100)，接下来n行，每行m个字符，其中:‘w’、‘W’、‘f’分别代表那三个人；‘.’代表没有障碍物的格子，‘#’代表有障碍物的格子。
输出
每组数据输出一行。
样例输入
4 4
w...
####
.##f
W##.
4 4
w...
....
.##f
.W..
样例输出
2
0
BFS、枚举中间点
#include <iostream>#include <algorithm>#include <cstdio>#include <queue>#include <cstring>#include <cmath>using namespace std;#define INF 0x7fffffff#define N 110struct node{ int x,y;};int n,m;node p[4];char mpt[N][N];int vis[N][N][4];int dir[4][2]={1,0,-1,0,0,1,0,-1};void bfs(int index){ queue<node> q; node now,next; now.x=p[index].x; now.y=p[index].y; q.push(now); vis[now.x][now.y][index]=0; while(!q.empty()) { now=q.front(); q.pop(); for(int i=0;i<4;i++) { next=now; next.x+=dir[i][0]; next.y+=dir[i][1]; if(next.x<1 || next.x>n || next.y<1 || next.y>m) continue; int tmp=vis[now.x][now.y][index]; if(mpt[next.x][next.y]==‘#‘) tmp++; if(tmp<vis[next.x][next.y][index]) { vis[next.x][next.y][index]=tmp; q.push(next); } } }}int main(){while(scanf("%d%d",&n,&m)!=EOF) { for(int k=1;k<=3;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { vis[i][j][k]=INF; } } } for(int i=1;i<=n;i++) { scanf("%s",mpt[i]+1); } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(mpt[i][j]==‘w‘) p[1].x=i,p[1].y=j; else if(mpt[i][j]==‘W‘) p[2].x=i,p[2].y=j; else if(mpt[i][j]==‘f‘) p[3].x=i,p[3].y=j; } } bfs(1); bfs(2); bfs(3); int ans=INF; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int tmp=0; for(int k=1;k<=3;k++) { tmp+=vis[i][j][k]; } if(mpt[i][j]==‘#‘) tmp-=2; if(tmp<ans) ans=tmp; } } cout<<ans<<endl; } return 0;}
BFS [SWUST OJ 191] 迷宫逃离
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。