This is quite an easy problem. But it took me long time to realize that to determine the number of total game segments is nothing but counting the direction changes to reach the destination.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
#include <iostream> #include <cstdio> #include <climits> #include <queue> #include <cstring> #include <string> using namespace std; int w,h; int SEGMENT; int gr[80][80]; int visit[80][80]; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; int bfs(int stx,int sty,int edx,int edy) { int x,y,stp; int direction=0,tmpDirection; int tmpx,tmpy; queue<int> q; memset(visit,0,sizeof(visit)); int step=0; q.push(stx); q.push(sty); q.push(step); q.push(direction); while(!q.empty()) { x = q.front();q.pop(); y = q.front();q.pop(); stp = q.front();q.pop(); direction = q.front();q.pop(); visit[x][y]=1; for(int i=0;i<4;i++) { if(x+dx[i]==edx && y+dy[i]==edy) { if(dx[i]==0) tmpDirection=1;//horizontal direction else if(dy[i]==0) tmpDirection=2;//vertical direction if(tmpDirection!=direction) return stp+1; return stp; } if(x+dx[i]>=0 && x+dx[i]<=(h+1) && y+dy[i]>=0 && y+dy[i]<=(w+1) && visit[x+dx[i]][y+dy[i]]==0 && gr[x+dx[i]][y+dy[i]]==0) { tmpx = x+dx[i]; tmpy = y+dy[i]; q.push(x+dx[i]); q.push(y+dy[i]); if(dx[i]==0) tmpDirection=1;//horizontal direction else if(dy[i]==0) tmpDirection=2;//vertical direction if(tmpDirection!=direction) q.push(stp+1); else if(tmpDirection==direction) q.push(stp); q.push(tmpDirection); } } } return -1; } int main() { char ch; int kase=1; string str; vector<int> path; int x1,x2,y1,y2; while(scanf("%d%c%d%c",&w,&ch,&h,&ch),w,h) { memset(gr,0,sizeof(gr)); for(int i=1;i<=h;i++) { getline(cin,str); for(int j=0;j<w;j++) { if(str[j]=='X') gr[i][j+1]=1; else if(str[j]==' ') gr[i][j+1]=0; } } bool flag=0; int ccase=1; int res; while(scanf("%d%c%d%c%d%c%d%c",&x1,&ch,&y1,&ch,&x2,&ch,&y2,&ch)) { if(x1+y1+x2+y2==0) break; res = bfs(y1,x1,y2,x2); if(flag==0) printf("Board #%d:\n",kase++); flag = 1; if(res==-1) printf("Pair %d: impossible.\n",ccase++); else printf("Pair %d: %d segments.\n",ccase++,res); } printf("\n"); } return 0; } |