https://vjudge.net/problem/UVA-816
题目
Robert Abbott发明了一些迷宫,1999年的ICPC世界总决赛中一道题目的背景就是他发明的一种迷宫,还是厉害……然后2000年的ICPC世界总决赛又有他的迷宫了,好凶啊!
就是这种
貌似现实中还建了这种迷宫,不过我在网上没有搜到。
然后扯Knuth半小时就解决了这个问题……
具体走法还是看原题……(我语文不好)
题解
【以下内容除了代码都是废话】
bfs,多了判断走法的部分
如果是直走就保持当前方向不变,如果左转就逆时针旋转90度,右转就顺时针旋转90度,然后朝新方向走一步
一旦到达终点肯定是最短路径,因为后面的队列只会保持长度不变或增加(翻译腔?)
方向用了enum……c++11不支持enum class隐式转int,用了enum(上了xuetangx的c++课才知道……)至于怎么转……(int)(没有仔细研究过,工程上才用吧)
https://en.cppreference.com/w/cpp/language/enum
代码很乱,UVA又挂了,在ICPC Live Archive上交的
等UVA好了再写一遍(咕咕咕)
AC代码
#include<bits/stdc++.h> using namespace std; #define REP(i,x,y) for(register int i=(x); i<(y); i++) #define REPE(i,x,y) for(register int i=(x); i<=(y); i++) #ifdef LOCAL #define DBG(a,...) printf(a, ##__VA_ARGS__) #else #define DBG(a,...) (void)0 #endif #define MAXN 13 char title[27]; enum way{_L, _F, _R}; enum di{_N, _E, _S, _W};//shun bool E[MAXN][MAXN][4][3]; struct node { int x,y,way; int lst; }; node st, ed; node ans[450]; int ansf, ansr; int vis[MAXN][MAXN][4]; const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1}; inline void bfs() { memset(vis,0x3f,sizeof vis); ansf=ansr=0; // st.lst=-1; int nx = st.x+dx[st.way]; int ny = st.y+dy[st.way]; ans[ansf++]=((node){nx,ny,st.way,-1}); // vis[st.x][st.y][st.way]=0; vis[nx][ny][st.way]=0; bool f =false; while(ansf>ansr) { node now = ans[ansr++]; if(now.x==ed.x && now.y==ed.y) {f=true;break;} REP(i,0,3) { int nw = now.way+i-1; if(nw<0) nw+=4; if(nw>=4) nw-=4; int nx = now.x+dx[nw]; int ny = now.y+dy[nw]; if(E[now.x][now.y][now.way][i] && vis[nx][ny][nw]> vis[now.x][now.y][now.way]+1) { ans[ansf++]=((node){nx,ny,nw,ansr-1}); vis[nx][ny][nw]=vis[now.x][now.y][now.way]+1; } } } if(!f) { printf(" No Solution Possible "); return; } ansr--; putchar(' '),putchar(' '); printf("(%d,%d)", st.x, st.y); stack<node> st; st.push(ans[ansr]); node &now = ans[ansr]; while(~now.lst) { now = ans[now.lst]; st.push(now); } int k=1; while(!st.empty()) { node now = st.top(); st.pop(); if(k==0) putchar(' '),putchar(' '); else putchar(' '); k++; printf("(%d,%d)", now.x, now.y); if(k==10) { k=0; putchar(' '); } } if(k) putchar(' '); } inline bool getli(char *p) { *p = getchar(); while(*p<' ') *p=getchar(); while(*p!=' ' && *p!=EOF) *(++p)=getchar(); *p=0; return true; } int main() { while(getli(title) && strcmp(title,"END")) { // DBG(title); memset(E,0,sizeof E); char stdir; scanf("%d%d%*c%c%d%d", &st.x, &st.y, &stdir, &ed.x, &ed.y); // DBG("%d %d %c %d %d", st.x, st.y, stdir, ed.x, ed.y); switch(stdir) { case 'N': st.way=_N; break; case 'E': st.way=_E; break; case 'S': st.way=_S; break; case 'W': st.way=_W; break; } int h,l; while(~scanf("%d", &h) && h) { scanf("%d", &l); char tmp[17]; while(1) { scanf("%s", tmp); if(*tmp=='*') break; int _l = strlen(tmp); switch(tmp[0]) { case 'N': tmp[0]=_N; break; case 'E': tmp[0]=_E; break; case 'S': tmp[0]=_S; break; case 'W': tmp[0]=_W; break; } REP(i,1,_l) switch(tmp[i]) { case 'F': E[h][l][tmp[0]][_F]=1; break; case 'L': E[h][l][tmp[0]][_L]=1; break; case 'R': E[h][l][tmp[0]][_R]=1; break; } } } puts(title); bfs(); } return 0; }