本文主要是介绍HDU1728 （BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
逃离迷宫
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 17526 Accepted Submission(s): 4257
第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数，接下来m行，每行包括n个字符，其中字符'.'表示该位置为空地，字符'*'表示该位置为障碍，输入数据中只有这两种字符，每组测试数据的最后一行为5个整数k, x 1, y 1, x 2, y 2 (1 ≤ k ≤ 10, 1 ≤ x 1, x 2 ≤ n, 1 ≤ y 1, y 2 ≤ m),其中k表示gloria最多能转的弯数，(x 1, y 1), (x 2, y 2)表示两个位置，其中x 1，x 2对应列，y 1, y 2对应行。
2 5 5 ...** *.**. ..... ..... *.... 1 1 1 1 3 5 5 ...** *.**. ..... ..... *.... 2 1 1 1 3
no yes
记着上次做了一次AC了，但是最近想总结一下BFS，在做的时候总是WR，后来才发现，细节的地方还是没有整明白。
引用大神的资料！ http://972169909-qq-com.iteye.com/blog/1244218
【假如转弯数k=1,起点终点如图】
那么如果你的代码是优先向右搜索就会出错
红色的线是先搜的，由于最多转一次弯，所以不合题意；
蓝色是后搜的，因为遇到转弯数相等所以不往下走了了，但是继续走是可以满足题意输出"yes"的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define N 1100
struct Node{
int x,y,turn,pri_turn;
Node(){}
Node(int _x,int _y,int _t,int pri){
x =_x; y = _y;
turn = _t; pri_turn = pri;
}
};
const int xx[4] = {0,0,-1,1};
const int yy[4] = {1,-1,0,0};
char map[N][N];
int vis[N][N];
int n,m,k;
queue<Node> q;
void BFS(int &ans,int &x1,int &y1,int &x2,int &y2) {
while(!q.empty()) q.pop();
q.push(Node(x1,y1,-1,-1));
vis[x1][y1] = -1;
while(!q.empty()) {
Node cur = q.front(); q.pop();
if(cur.turn > k) continue;
if(cur.x == x2&&cur.y == y2) {
ans = 1; return;
}
for(int i = 0;i<4;i++) {
int t = (cur.pri_turn==i?cur.turn:(cur.turn+1));
Node tem = Node(cur.x+xx[i],cur.y+yy[i],t,i);
if(tem.x>n||tem.x<=0||tem.y<0||tem.y>=m) continue;
if(map[tem.x][tem.y]=='*') continue;
if(map[tem.x][tem.y]=='.'&&vis[tem.x][tem.y] >= tem.turn){// 考虑了1小时在这里，必须写成vis[tem.x][tem.y]>=tem.turn 必须是大于等于号
vis[tem.x][tem.y] = tem.turn;
q.push(tem);
}
}
}
ans = -1;
}
void init() {
memset(vis,0x0f0f0f0f,sizeof(vis));
}
void getData(int &x1,int &y1,int &x2,int &y2){
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++) scanf("%s",map[i]);
scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
y1--; y2--;
}
int main() {
int t,x1,y1,x2,y2;
//freopen("Test.txt","r",stdin);
scanf("%d",&t);
while(t--) {
init();
getData(x1,y1,x2,y2);
int ans = -1;
BFS(ans,x1,y1,x2,y2);
if(ans == -1) printf("no\n");
else printf("yes\n");
}
return 0;
}
这篇关于HDU1728 （BFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
