第六章部分例题

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("
");
 70     }
 71 
 72     if(nodes.size()%10!=0) printf("
");
 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
");
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 }
Yosoro