HDU 3085 Nightmare Ⅱ (双向BFS)
Nightmare Ⅱ
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 886 Accepted Submission(s): 185
1 #include <iostream> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdio> 5 #include <queue> 6 using namespace std; 7 8 const int SIZE = 805; 9 const int UPDATE[][2] = {{-1,0},{1,0},{0,-1},{0,1}}; 10 int N,M; 11 int STEP; 12 int MAP[SIZE][SIZE]; 13 int VIS_1[SIZE][SIZE],VIS_2[SIZE][SIZE]; 14 int Z_X_1,Z_Y_1,Z_X_2,Z_Y_2; 15 16 struct Node 17 { 18 int x,y; 19 bool check(void) 20 { 21 if(x >= 1 && x <= N && y >= 1 && y <= M && MAP[x][y] != ‘X‘ 22 && (abs(Z_X_1 - x) + abs(Z_Y_1 - y) > 2 * STEP) 23 && (abs(Z_X_2 - x) + abs(Z_Y_2 - y) > 2 * STEP)) 24 return true; 25 return false; 26 } 27 }; 28 29 int dbfs(Node boy,Node girl); 30 int main(void) 31 { 32 int t,ans,flag; 33 Node boy,girl; 34 char s[SIZE]; 35 36 scanf("%d",&t); 37 while(t --) 38 { 39 flag = 1; 40 scanf("%d%d",&N,&M); 41 getchar(); 42 for(int i = 1;i <= N;i ++) 43 { 44 scanf("%s",&s[1]); 45 for(int j = 1;j <= M;j ++) 46 { 47 MAP[i][j] = s[j]; 48 if(MAP[i][j] == ‘M‘) 49 { 50 boy.x = i; 51 boy.y = j; 52 } 53 else if(MAP[i][j] == ‘G‘) 54 { 55 girl.x = i; 56 girl.y = j; 57 } 58 else if(MAP[i][j] == ‘Z‘ && flag) 59 { 60 Z_X_1 = i; 61 Z_Y_1 = j; 62 flag = 0; 63 } 64 else if(MAP[i][j] == ‘Z‘) 65 { 66 Z_X_2 = i; 67 Z_Y_2 = j; 68 } 69 } 70 } 71 72 ans = dbfs(boy,girl); 73 printf("%d\n",ans); 74 } 75 76 return 0; 77 } 78 79 int dbfs(Node boy,Node girl) 80 { 81 memset(VIS_1,0,sizeof(VIS_1)); 82 memset(VIS_2,0,sizeof(VIS_2)); 83 VIS_1[boy.x][boy.y] = 1; 84 VIS_2[girl.x][girl.y] = 1; 85 STEP = 1; 86 87 queue<Node> que_boy,que_girl; 88 que_boy.push(boy); 89 que_girl.push(girl); 90 91 while(1) 92 { 93 for(int i = 0;i < 3;i ++) 94 { 95 int size = que_boy.size(); 96 while(size --) 97 { 98 Node old = que_boy.front(); 99 que_boy.pop(); 100 if(!old.check()) 101 continue; 102 103 for(int j = 0;j < 4;j ++) 104 { 105 Node cur = old; 106 107 cur.x += UPDATE[j][0]; 108 cur.y += UPDATE[j][1]; 109 if(!cur.check() || VIS_1[cur.x][cur.y]) 110 continue; 111 if(VIS_2[cur.x][cur.y]) 112 return STEP; 113 114 VIS_1[cur.x][cur.y] = 1; 115 que_boy.push(cur); 116 } 117 } 118 } 119 120 if(que_girl.empty() && que_boy.empty()) 121 return -1; 122 if(que_girl.empty()) 123 continue; 124 125 int size = que_girl.size(); 126 while(size --) 127 { 128 Node old = que_girl.front(); 129 que_girl.pop(); 130 if(!old.check()) 131 continue; 132 133 for(int j = 0;j < 4;j ++) 134 { 135 Node cur = old; 136 137 cur.x += UPDATE[j][0]; 138 cur.y += UPDATE[j][1]; 139 if(!cur.check() || VIS_2[cur.x][cur.y]) 140 continue; 141 if(VIS_1[cur.x][cur.y]) 142 return STEP; 143 144 VIS_2[cur.x][cur.y] = 1; 145 que_girl.push(cur); 146 } 147 } 148 STEP ++; 149 } 150 151 return -1; 152 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。