还是以前看不懂的一个题目，现在回头看起来 水死了 ，但是好像让我写也是写不出来的。对照着网上的实现。也算全部理解了，代码都经过我详细注释。里面感觉有很多 搜索的惯用思维方法，应该学会如何把这种常见问题抽象成代码方案。比如如何判断行走的方法。学会怎么刻画最短路径搜索树！
#include<iostream>#include<sstream>#include<algorithm>#include<cstdio>#include<string.h>#include<cctype>#include<string>#include<cmath>#include<vector>#include<stack>#include<queue>#include<map>#include<set>using namespace std;const int INF=0x1f1f1f1f;const double pi=4*atan(1);const int Maxn=200+10;int dr[]= {-1,0,1,0};//两数组控制行数和列数，此程序中int dc[]= {0,1,0,-1};//数组元素特定struct Node //每一个节点的属性集合 包含横纵坐标和 面朝方向{//这里的方面dir是int值对应方向char数组元素下标int r,c,dir;Node(int rr,int cc,int dirr):r(rr),c(cc),dir(dirr) {}Node() {}};const char *dirs="NESW"; // 常量数组运用const char *turns="FLR";bool has_edge[10][10][4][4];// 前两个元素表示横纵坐标，第三四个分别表示面朝某一方向时，是否可以转弯int d[10][10][4];// bfs时，，记录行走长度int r1,c1,r2,c2,dir;int r0,c0;bool flag;Node p[10][10][4]; //保存最短路径树的父节点，记录路径int dir_id(char ch)// 将字符方向双射到int表示的方向{return strchr(dirs,ch)-dirs;}int turn_id(char ch) // 同样把用字符表示的向哪儿转双射到int上{return strchr(turns,ch)-turns;}//根据当前状态，和所要转弯方式，计算后继状态：//行走函数：Node walk(Node &u,int turn ){int dd=u.dir;if(turn==1) // 逆时针dd=(dd+3)%4;else if(turn == 2) //顺时针dd=(dd+1)%4;return Node(u.r+dr[dd],u.c+dc[dd],dd);// 返回后继状态}//从目标结点逆序追溯到初始结点void print_ans(Node u){vector<Node>nodes;while(1){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)cout<<" ";cout<<" ("<<nodes[i].r<<","<<nodes[i].c<<")";if(++cnt%10==0)cout<<endl;}if(nodes.size()%10!=0)cout<<endl;}bool inside(int r,int c){if(r>0&&r<10&&c>0&&c<10)return true ;return false;}void solve(){queue<Node>q;memset(d,-1,sizeof(d));memset(p,0,sizeof(p));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) //发现终点退出{flag=0;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(){char str[30];while(scanf("%s",str)&&strcmp(str,"END")){flag=1;memset(has_edge,0,sizeof(has_edge));char ch;cin>>r0>>c0>>ch>>r2>>c2;dir=dir_id(ch);r1=r0+dr[dir];c1=c0+dc[dir];int r,c;char str2[30];while(cin>>r){if(r==0)break;cin>>c;while(cin>>str2){if(str2[0]=='*')break;int dirID=dir_id(str2[0]);int len=strlen(str2);for(int i=1; i<len; i++){int turnID=turn_id(str2[i]);has_edge[r][c][dirID][turnID]=1;}}}printf("%s\n",str);solve();}return 0;}
不知道来年，会不会开出一地的记忆和忧愁。
