Untitled
plain_text
2 months ago
2.3 kB
0
Indexable
Never
#include <iostream> using namespace std; int qe[2000000]; int dx[] = {-2,-2,-1,-1,1,1,2,2}; int dy[] = {-1,1,-2,2,-2,2,-1,1}; int A[1000][1000]= {0}; int head; int tail; void enq(int x){ tail++; qe[tail] = x; } int deq(){ head++; int x = qe[head]; return x; } int main(){ freopen("input.txt","r",stdin); int T,x; cin>>T; for (x = 0; x < T; x++){ int N,M; cin>>N>>M; int R,C,S,K; cin>>R>>C>>S>>K; R--;C--;S--;K--; head = -1; tail = -1; int check = 0; enq(R); enq(C); A[R][C] = 0; while (tail - head >=2){ int row = deq(); int col = deq(); for (int k = 0; k < 8; k++){ int x1 = row + dx[k]; int y1 = col + dy[k]; if (x1>=0 && y1>=0 && x1<N && y1<M && A[x1][y1] == 0){ enq(x1); enq(y1); A[x1][y1] = A[row][col] + 1; if (x1 == S && y1 == K){ check = 1; break; } } } if (check ==1) break; } cout <<"Case #"<<x+1<<endl<<A[S][K]<<endl; for (int i = 0; i < N; i++) for (int j = 0; j < M ; j++) A[i][j] = 0; } return 0; } /* 50 9 9 2 2 4 4 20 20 2 3 7 9 5 5 1 1 2 2 522 55 292 23 84 6 176 361 110 244 118 191 870 435 352 166 93 238 67 192 23 108 16 179 63 521 7 397 45 182 136 738 100 613 46 351 599 504 401 52 561 216 620 639 412 330 185 323 767 206 659 191 710 26 745 467 681 447 392 382 601 607 332 467 53 249 593 604 271 182 35 231 787 404 193 168 121 121 537 793 487 328 354 665 42 685 7 281 6 15 37 105 28 23 35 21 506 367 316 319 340 350 67 606 37 226 23 44 718 586 255 252 517 359 824 283 735 262 734 236 304 452 62 99 228 16 431 259 236 256 262 252 83 550 4 439 8 134 423 358 331 78 222 232 89 663 84 518 35 489 158 309 25 182 66 99 331 732 147 83 228 603 637 772 83 616 263 671 98 384 1 86 52 146 500 549 104 124 383 504 245 800 51 545 224 82 530 310 55 260 499 122 796 736 784 715 422 49 830 141 304 126 540 115 188 216 167 200 77 95 877 833 103 417 586 434 78 814 31 476 45 547 718 205 183 49 264 72 1000 1000 792 263 984 381 1000 1000 916 535 918 910 1000 1000 471 862 103 836 1000 1000 305 86 952 411 1000 1000 687 39 56 237 1000 1000 238 685 477 979 1000 1000 50 647 35 902 1000 1000 375 265 305 481 1000 1000 178 33 150 91 */