首页 > 代码库 > poj-2312
poj-2312
题意:
这个题是以坦克大战为原型出来的题目,就是走迷宫的变种,给定一个地图mxn的地图,地图上有普通的砖B,金砖S,河R,空地E,和一个宝物位置T,和你的位置Y,求吃到宝物的最小步数(坦克通过普通砖B需要两步,空地E一步,不能通过金砖和河)..
样例输入
3 4 YBEB EERE SSTE 0 0
样例输出
8
解题思路:
简单的BFS但是要用优先队列来做,普通的队列会出错(很重要),不过目前还没弄清楚出错的原因。
具体代码:
#include<iostream> #include<queue> #include<cstring> using namespace std; char map[305][305]; int beginx,beginy; int m,n; int fangxiang[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int res=9999999; //int min=1000000; struct Node { int x; int y; int step; Node (int x1,int y1,int step1):x(x1),y(y1),step(step1){} }; bool operator < (const Node &a, const Node &b) //优先队列,队头为最优解。即花费最少 { return a.step > b.step; } void bfs(int p,int q,int ste) { priority_queue<Node> qq; Node node(p,q,ste); while(!qq.empty()) qq.pop(); qq.push(node); while(!qq.empty()) { node=qq.top(); qq.pop(); if(map[node.x][node.y]==‘T‘) { if(node.step<res) { res=node.step; } } for(int i=0;i<4;i++) { int xx=node.x+fangxiang[i][0]; int yy=node.y+fangxiang[i][1]; if(xx>=1&&xx<=m&&yy>=1&&yy<=n&&(map[xx][yy]==‘E‘||map[xx][yy]==‘B‘||map[xx][yy]==‘T‘)) { if(map[xx][yy]!=‘T‘) { if(map[xx][yy]==‘B‘) { map[xx][yy]=‘S‘; Node test(xx,yy,node.step+2); qq.push(test); } else if(map[xx][yy]==‘E‘) { map[xx][yy]=‘S‘; Node test(xx,yy,node.step+1); qq.push(test); } } else { Node test(xx,yy,node.step+1); qq.push(test); } } } } } int main() { while(1) { memset(map,0,sizeof(map)); res=9999999; cin>>m>>n; if(m+n==0) break; else { for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { cin>>map[i][j]; if(map[i][j]==‘Y‘) { beginx=i; beginy=j; } } } bfs(beginx,beginy,0); if(res!=9999999) cout<<res<<endl; else cout<<-1<<endl; } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。