首页 > 代码库 > uva 816 Abbott的复仇
uva 816 Abbott的复仇
题目链接：https://uva.onlinejudge.org/external/8/816.pdf
紫书：P165
题意：
有一个最多包含9*9个交叉点的迷宫。输入起点、离开起点时的朝向和终点，求一条最短路（多解时任意输出一个即可）。
分析：
BFS的结点对状态转移的影响的因素有哪些，那么这个结点就要包含哪些信息。
左右，和东南西北的转换。
首先规定东南西北的顺时针。根据左右转向求出下一个方位。
下一个节点的坐标是有当前位置，和下一个状态的方向决定。
图的构建也是根据对结点状态转移的影响建图的。 has_edge[r][c][dir][turn] ，当前状态(r,c,dir)向 turn 方向走是否有路。
#include <bits/stdc++.h>using namespace std;struct Node{ int r,c,dir; Node (int r=0,int c=0,int dir = 0) : r(r),c(c),dir(dir) {}};const int Maxn = 10;const char* dirs = "NESW";const char* turns = "FLR";int dir_id(char c){ return strchr(dirs,c) - dirs;}int turn_id(int c){ return strchr(turns,c) - turns;}const int dr[] = {-1,0,1,0};const int dc[] = {0,1,0,-1};Node walk(const Node& u,int turn){ int dir = u.dir; if(turn==1) dir = (dir - 1 + 4)%4; ///向左转 if(turn==2) dir = (dir+ 1)%4; ///向右转 return Node(u.r+dr[dir],u.c+dc[dir],dir);}bool inside(int r,int c){ if(r>=1&&r<=9&&c>=1&&c<=9) return true; else return false;}int has_edge[Maxn][Maxn][4][3];int r0,c0,r1,c1,r2,c2,dir;bool read(){ char s[99],s2[99]; if(scanf("%s%d%d%s%d%d",s,&r0,&c0,s2,&r2,&c2)!=6) return false; puts(s); dir = dir_id(s2[0]); r1 = r0 + dr[dir]; c1 = c0 + dc[dir]; memset(has_edge,0,sizeof(has_edge)); for(;;) { int r,c; scanf("%d",&r); if(r==0) break; scanf("%d",&c); while(scanf("%s",s)==1&&s[0]!=‘*‘) { for(int i=1; i<strlen(s); i++) { has_edge[r][c][dir_id(s[0])][turn_id(s[i])] = 1; } } } return true;}int d[Maxn][Maxn][4];Node p[Maxn][Maxn][4];void print_ans (Node u){ vector<Node> nodes; for(;;) { nodes.push_back(u); if(d[u.r][u.c][u.dir]==0) break; u = p[u.r][u.c][u.dir]; } nodes.push_back(Node(r0,c0,dir)); int cnt = 0; for(int i=nodes.size()-1; i>=0; i--) { if(cnt%10==0) printf(" "); printf(" (%d,%d)",nodes[i].r,nodes[i].c); cnt++; if(cnt%10==0) printf("\n"); } if(nodes.size()%10!=0) puts("");}void bfs(){ queue<Node> q; memset(d, -1, sizeof(d)); Node u(r1, c1, dir); d[u.r][u.c][u.dir] = 0; q.push(u); while(!q.empty()) { Node u = q.front(); q.pop(); if(u.r == r2 && u.c == c2) { print_ans(u); return; } for(int i = 0; i < 3; i++) { Node v = walk(u, i); if(has_edge[u.r][u.c][u.dir][i] && inside(v.r, v.c) && d[v.r][v.c][v.dir] < 0) { d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1; p[v.r][v.c][v.dir] = u; q.push(v); } } } printf(" No Solution Possible\n");}int main(){ while(read()) { bfs(); } return 0;}
uva 816 Abbott的复仇
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。