HDU 1728 逃离迷宫 BFS题
題目描述：輸入一個m*n的地圖，地圖上有兩種點，一種是 . 表示這個點是空地，是可以走的，另一種是 * ，表示是墻，是不能走的，然后輸入一個起點和一個終點，另外有一個k輸入，現在要你確定能否在轉k次彎之前從起點到達終點。
解題報告：首先說下這題坑的地方，就是輸入起點和終點的坐標的時候，不是按照x1,y1,x2,y2輸入的，而是按照y1,x1,y2,x2的順序輸入的。這題搞了很久 ，就是一開始沒有想到怎么解決得到最小轉彎次數的方法，一開始試過重復訪問點，但是這樣超內存了，然后如果不重復訪問的話又會得不到轉彎次數最小的點，就是說假如一個點從一條路線上被更新過的話，下一次從另一條路線上就不能再一次更新了，即使如果按照第二次走的路線轉彎的次數會更少的 話。看了別人解題報告才想到，可以這樣來解決就是當走到一個點時，如果可以沿著這條線直走的話，就一直走下去，除非到了邊界，或者碰到墻，同時是否將這點放入隊列的話也要做出相應的 改變，因為走的時候只要不是墻都能走，但是 不能把所有的點都放進隊列，所以我們可以將從沒有走過并且是可以走的點放進隊列，而把已經走過的點不放進隊列，這樣就可以解決超內存的問題了，另外，走完當前這個點之后，不要忘了把這個點標記為已經走過。并且每次走之前判斷是否已經到達了終點、邊界，墻。一開始用自己寫的隊列發現代碼更長，時間也更長，后來改用deque雙端隊列來寫，首先代碼只寫了5分鐘，而且沒有調試一次就AC了，并且時間更短，內存更小，代碼也更短。這里把我手動寫的隊列的和用deque的代碼都附上。
手寫隊列代碼：
#include<cstdio>
#include<cstring>
#include<time.h>
const int MAX = +;
int T,m,n,k,x1,y1,x2,y2;
int xx[] = {-,,,}; //定義移動方向
int yy[] = {,,,-};
int map[MAX][MAX];
typedef struct node {
int x,y,dire,time; //dire用來保存當前的方向，time表示走到當前步為止，轉彎的次數
node() {
dire = time = ;
}
node *next;
}*LinkList,linklist;
bool bfs() {
LinkList head = NULL,p = NULL,temp;
head = new linklist; //新建隊列頭結點，頭結點不放元素
p = new linklist; //便于存取節點
p->next = NULL;
p->x = x1,p->y =y1; //首先將起點加到隊尾
head->next = p;
while(head->next!=NULL) {
temp = head->next; //將節點從隊首取出
if(temp->x ==x2 && temp->y==y2 && temp->time-<k)
return true; //判斷是否已經到達終點
for(int i = ;i<;++i) { //從當前的位置向周圍四個方向走
int xxx = temp->x + xx[i];
int yyy = temp->y + yy[i];
if(xxx<||xxx>m||yyy<||yyy>n)
continue;
while(map[xxx][yyy]==||map[xxx][yyy]==) { //這一步很重要，如果當前走的方向是直的，且可走，則一直走到底，
//但只有從沒有走過的點才加入到隊列中
if(xxx<||xxx>m||yyy<||yyy>n)
break;
if(xxx ==x2 && yyy==y2 && temp->time-<k)
return true; LinkList q = new linklist;
q->next = NULL;
q->x = xxx;
q->y = yyy;
q->dire = i+;
q->time = temp->time;
if(temp->dire != q->dire)
q->time++;
if(!map[xxx][yyy]) { //從沒走過的點才加入到隊列中
q->next = p->next;
p->next = q;
p = p->next;
}
else delete q; //否則刪除新建的這個點
map[xxx][yyy] = ; //走過之后標記為已走過，這一順序，這句不能放前面
yyy+=yy[i];
xxx+=xx[i];
}
}
head->next = temp->next;
delete temp;
}
return false;
} int main() {
char d;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&m,&n);
memset(map,,sizeof(map));
for(int i = ;i<=m;++i) {
getchar();
for(int j = ;j<=n;++j) {
scanf("%c",&d);
if(d == '*')
map[i][j] = ;
}
}
scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
printf(bfs()? "yes\n":"no\n");
}
return ;
}
deque代碼：
#include<cstdio>
#include<deque>
#include<iostream>
#include<cstring>
using namespace std;
const int MAX = +;
int k,x1,y1,x2,y2,m,n;
int xx[] = {-,,,};
int yy[] = {,,,-};
class node {
public:
int map[MAX][MAX];
bool bfs();
private:
struct Linklist {
int x,y,dire,times;
Linklist() {
dire = times = ;
}
};
};
bool node::bfs() {
deque<Linklist> head;
Linklist p;
p.x = x1,p.y = y1;
head.push_back(p);
deque<Linklist>::iterator iter;
while(head.size()!=) {
iter = head.begin();
for(int i = ;i<;++i) {
int xxx = iter->x + xx[i];
int yyy = iter->y + yy[i];
if(xxx<||xxx>m||yyy<||yyy>n)
continue;
while(map[xxx][yyy]!=) {
if(xxx == x2 && yyy ==y2 && iter->times-<k)
return true;
Linklist q;
q.x = xxx,q.y = yyy;
q.dire = i+;
q.times = iter->times;
if(q.dire != iter->dire)
q.times++;
if(map[xxx][yyy]==)
head.push_back(q);
map[xxx][yyy] = ;
xxx += xx[i];
yyy += yy[i];
if(xxx<||xxx>m||yyy<||yyy>n)
break;
}
}
head.pop_front();
}
return false;
}
int main() {
int T;
char c;
node temp;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&m,&n);
memset(temp.map,,sizeof(temp.map));
for(int i = ;i<=m;++i) {
getchar();
for(int j = ;j<=n;++j) {
scanf("%c",&c);
if(c == '*')
temp.map[i][j] = ;
}
}
scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
printf(temp.bfs()? "yes\n":"no\n");
}
return ;
}
總結
以上是生活随笔為你收集整理的HDU 1728 逃离迷宫 BFS题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Rocket - util - Asyn
- 下一篇： jQueryEasyUI