锐客网

  1. 首页 > it技术 > >

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; }


    推荐阅读


    上一篇：数据分析|NLP中关于文本分类问题的常用方案

    下一篇：真相大白！韩国著名演员承认性犯罪，韩影界遭受大冲击！