uva 816
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <vector> 6 #include <sstream> 7 8 using namespace std; 9 10 struct Node 11 { 12 int r,c,dir; 13 14 Node(int rx,int cx,int dirx):r(rx),c(cx),dir(dirx){} 15 Node(){} 16 }; 17 18 19 const int maxn=11; 20 int has_edge[maxn][maxn][4][3],d[maxn][maxn][4]; 21 Node p[maxn][maxn][4]; 22 23 int r0,c0,r1,c1,r2,c2; 24 char dir0,dir1; 25 26 const char* dirs="NESW"; 27 const char* turns="FLR"; 28 29 int dir_id(char dir) { return strchr(dirs,dir)-dirs;} 30 int turn_id(char turn) { return strchr(turns,turn)-turns;} 31 32 const int dr[]={-1,0,1,0}; 33 const int dc[]={0,1,0,-1}; 34 35 Node walk(Node n,int i) 36 { 37 int dir=n.dir; 38 39 if(i==1) dir=(dir+3)%4; 40 if(i==2) dir=(dir+1)%4; 41 42 return Node(n.r+dr[dir],n.c+dc[dir],dir); 43 } 44 45 void print_ans(Node node) 46 { 47 vector<Node> nodes; 48 49 for(;;) 50 { 51 52 int r=node.r; 53 int c=node.c; 54 int dir=node.dir; 55 56 nodes.push_back(node); 57 58 if(d[r][c][dir]==0) break; 59 60 node=p[r][c][dir]; 61 62 } 63 64 int cnt=0; 65 for(int i=nodes.size()-1;i>=0;i--) 66 { 67 if(cnt%10==0) printf(" "); 68 printf(" (%d,%d)",nodes[i].r,nodes[i].c); 69 if(++cnt %10==0) printf("\n"); 70 } 71 72 if(nodes.size()%10!=0) printf("\n"); 73 } 74 75 void bfs() 76 { 77 78 Node u=Node(r1,c1,dir_id(dir1)); 79 p[r1][c1][dir_id(dir1)]=Node(r0,c0,dir_id(dir0)); 80 d[r0][c0][dir_id(dir0)]=0; 81 d[r1][c1][dir_id(dir1)]=1; 82 83 queue<Node> q; 84 85 q.push(u); 86 87 while(!q.empty()) 88 { 89 Node newn=q.front(); 90 q.pop(); 91 92 int r,c,dir; 93 94 r=newn.r; 95 c=newn.c; 96 dir=newn.dir; 97 98 if(r==r2 && c==c2) { print_ans(newn); return;} 99 100 for(int i=0;i<3;i++) 101 { 102 if(has_edge[r][c][dir][i]) 103 { 104 Node nextn=walk(newn,i); 105 106 if(d[nextn.r][nextn.c][nextn.dir]<0) 107 { 108 d[nextn.r][nextn.c][nextn.dir]=d[newn.r][newn.c][newn.dir]+1; 109 p[nextn.r][nextn.c][nextn.dir]=newn; 110 q.push(nextn); 111 } 112 } 113 } 114 115 } 116 117 printf("NO SOLUTIONS\n"); 118 } 119 120 int main() 121 { 122 string name; 123 124 while(cin>>name && name!="END") 125 { 126 127 memset(p,0,sizeof(p)); 128 memset(has_edge,0,sizeof(has_edge)); 129 memset(d,-1,sizeof(d)); 130 131 cin>>r0>>c0>>dir0; 132 cin>>r2>>c2; 133 134 /* 135 cout<<"r0="<<r0<<endl; 136 cout<<"c0="<<c0<<endl; 137 cout<<"dir0="<<dir0<<endl; 138 cout<<"r2="<<r2<<endl; 139 cout<<"c2="<<c2<<endl; 140 141 */ 142 r1=r0+dr[dir_id(dir0)]; 143 c1=c0+dc[dir_id(dir0)]; 144 dir1=dir0; 145 146 /* 147 cout<<"r1="<<r1<<endl; 148 cout<<"c1="<<c1<<endl; 149 150 */ 151 152 string line; 153 154 getchar(); //c2后还有个回车所以要先接受 155 while(getline(cin,line) && line!="0") 156 { 157 //cout<<"line:"<<line<<endl; 158 159 stringstream ss(line); 160 161 int r,c; 162 ss>>r>>c; 163 164 string str; 165 while(ss>>str && str[0]!='*') 166 { 167 168 //cout<<"str:"<<str<<endl; 169 int dir=dir_id(str[0]); 170 171 for(int i=1;i<str.size();i++) 172 { 173 int turn=turn_id(str[i]); 174 175 has_edge[r][c][dir][turn]=1; 176 } 177 178 } 179 180 ss.clear(); 181 } 182 183 cout<<name<<endl; 184 bfs(); 185 } 186 187 return 0; 188 }
转载于:https://www.cnblogs.com/tclan126/p/7300224.html
相关资源：数据结构—成绩单生成器