首页 > 代码库 > POJ 3984 迷宫问题 BFS+路径保存
POJ 3984 迷宫问题 BFS+路径保存
题目链接:
思路:STL果然不是万能的。。写了一个下午。。。 改用普通数组写一会便过了。。真坑。。 主要就是建立一个保存前驱的数组
代码:
#include <iostream> #include <cstdio> #include <queue> using namespace std; int a[6][6]; int go[4][2] = {1,0,0,1,-1,0,0,-1}; struct node { int x; int y; }q[100]; int pre[100]; bool check(int x,int y) { if(x<0||x>4||y<0||y>4||a[x][y]==1) return false; else return true; } void print(int a) { if(a==0) { cout<<"("<<q[0].x<<", "<<q[0].y<<")"<<endl; return; } else { print(pre[a]); cout<<"("<<q[a].x<<", "<<q[a].y<<")"<<endl; } } int main() { // freopen("data.txt","r",stdin); for(int i=0;i<5;i++) { for(int j=0;j<5;j++) { cin>>a[i][j]; } } int t; int head = 0; int tail = 1; q[head].x = 0; q[head].y = 0; while(head!=tail) { if(q[head].x==4 && q[head].y==4) { break; } for(int i=0;i<4;i++) { if(check(q[head].x+go[i][0],q[head].y+go[i][1])) { q[tail].x = q[head].x+go[i][0]; q[tail].y = q[head].y+go[i][1]; pre[tail] = head; a[q[head].x][q[head].y] = 1; tail++; } } head++; } print(head); return 0; }
POJ 3984 迷宫问题 BFS+路径保存
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。