POJ 1475 Pushing Boxes 搜索

搜索这种东西只要写之前规划得当还是蛮顺手的。。
mark[x1][y1][x2][y2]表示小人在(x1,y1) 盒子在(x2,y2)这种状态是否到过。
【POJ 1475 Pushing Boxes】剩下的就是优先队列 + bfs 了，另外开一个栈记录前驱以输出路径。

#include #include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long #define _LL __int64 #define _INF 0x3f3f3f3f #define Mod 9999991using namespace std; char Map[24][24]; int mark[22][22][22][22]; struct N { int x1,x2,y1,y2; }; struct Q { int ans,x1,y1,x2,y2,pre; int ans2,site; bool operator < (const Q &a)const{ return (a.ans2 < ans2 || (a.ans2 == ans2 && a.ans < ans)); } }q[200000]; bool Judge(Q f) { if(abs(f.x1-f.x2) + abs(f.y1-f.y2) <= 1) return true; return false; }int jx[] = {-1, 1, 0, 0}; int jy[] = { 0, 0,-1, 1}; void Out(int site,Q f) { if(site == -1) return ; Out(q[site].pre,q[site]); Q t = q[site]; if(t.x1 == f.x1) { if(t.y1+1 == f.y1) { if(t.x2 == f.x2 && t.y2+1 == f.y2) { printf("E"); } else { printf("e"); } } else if(t.y1-1 == f.y1) { if(t.x2 == f.x2 && t.y2-1 == f.y2) { printf("W"); } else { printf("w"); } } } else if(t.y1 == f.y1) { if(t.x1+1 == f.x1) { if(t.y2 == f.y2 && t.x2+1 == f.x2) { printf("S"); } else { printf("s"); } } else if(t.x1-1 == f.x1) { if(t.y2 == f.y2 && t.x2-1 == f.x2) { printf("N"); } else { printf("n"); } } } }void bfs(N s,int n,int m) { memset(mark,-1,sizeof(mark)); mark[s.x1][s.y1][s.x2][s.y2] = 0; priority_queue pq; Q f,t; int S = 0,E = 0; f.ans = 0; f.ans2 = 0; f.pre = -1; f.x1 = s.x1; f.x2 = s.x2; f.y1 = s.y1; f.y2 = s.y2; f.site = 0; q[E++] = f; pq.push(f); while(pq.empty() == false) { f = pq.top(); pq.pop(); if(Map[f.x2][f.y2] == 'T') { Out(f.pre,f); puts(""); return ; }t.pre = f.site; t.ans = f.ans+1; for(int i = 0 ; i < 4; ++i) { t.x1 = f.x1 + jx[i]; t.y1 = f.y1 + jy[i]; t.x2 = f.x2; t.y2 = f.y2; if(1 <= t.x1 && t.x1 <= n && 1 <= t.y1 && t.y1 <= m && Map[t.x1][t.y1] != '#' && -1 == mark[t.x1][t.y1][t.x2][t.y2]) { if(t.x1 != t.x2 || t.y1 != t.y2) { mark[t.x1][t.y1][t.x2][t.y2] = t.ans; t.site = E; t.ans2 = f.ans2; q[E++] = t; pq.push(t); } else { t.x2 = f.x2 + jx[i]; t.y2 = f.y2 + jy[i]; if(1 <= t.x2 && t.x2 <= n && 1 <= t.y2 && t.y2 <= m && Map[t.x2][t.y2] != '#' && -1 == mark[t.x1][t.y1][t.x2][t.y2]) { t.ans2 = f.ans2+1; t.site = E; q[E++] = t; pq.push(t); mark[t.x1][t.y1][t.x2][t.y2] = t.ans; } } } } } printf("Impossible.\n"); }int main() { int i,j,n,m; int icase = 1; while(scanf("%d %d",&n,&m) && (n||m)) { for(i = 1; i <= n; ++i) scanf("%s",Map[i]+1); N s; for(i = 1; i <= n; ++i) { for(j = 1; j <= m; ++j) { if(Map[i][j] == 'S') s.x1 = i,s.y1 = j; else if(Map[i][j] == 'B') s.x2 = i,s.y2 = j; } } printf("Maze #%d\n",icase++); bfs(s,n,m); puts(""); } return 0; }

POJ 1475 Pushing Boxes

推荐阅读

竞技二打一的基本杀法破釜沉舟杀法

两岁宝宝可以吃香椿吗

小恐龙简笔画画法小恐龙简笔画教程

黄金现货价格最新

关于元宵节的祝福

红枣茯苓粥——清热除烦润泽肌肤

都说物以类聚,你会反对自家孩子结交坏学生吗？

榴莲打开肉是硬的还能放软吗榴莲有酒味是怎么回事还能吃吗!

几何画板证明勾股定理的详细方法几何画板证明勾股定理的详细方法

ipad用什么软件写代码，有可以在ipad上打php编程的软件吗有的请推荐一下

高铁能带水果刀吗乘坐高铁能不能带水果刀

口水鸡配料计口水鸡配料

靠谱的互联网金融平台有哪些推荐？

少年吃辣条＂中毒＂，抢救14小时仍未清醒！

雪花丸子怎么做最好吃窍门雪花丸子怎么做

丽江小倩现在还在丽江吗小倩丽江

word文档转xps格式，docx怎么转换成wps文档

bklal00是什么型号

尼康2470一代二代三代对比尼康2470二代

薇雅属于什么类型的电商公司薇雅属于什么类型的电商，薇雅属于什么类型的电商平台