Capture Knight
quoc14
c_cpp
21 days ago
4.6 kB
1
Indexable
Never
DFS and BFS
Capture Knight There is a mobile piece (a Knight) and a stationary piece on the N×M chessboard. The available moves of the mobile piece are the same as set out in the image below. You need to capture the stationary piece by moving the mobile piece with the minimum amount of moves. Write a program to find out the minimum number moves to catch a piece. [Input] Several test cases can be included in the inputs. T, the number of cases is given in the first row of the inputs. After that, the test cases as many as T are given in a row. N, the numbers of the rows and M, the number of columns of the chessboard are given in the first row of each test case. R & C is the location information of the attacking piece and S & K is the location of the defending pieces and are given in the row at the second line. However, the location of the uppermost end of the left end is (1, 1) Maximum value of N or M is 1000. [Output] Output the minimum number of movements to catch a defending piece at the first line of each test case. Print "Case #tn" before each answer where "tn" is test case number. [I/O Example] Input 2 9 9 3 5 2 8 20 20 2 3 7 9 Output Case #1 2 Case #2 5 Case #1 4 Case #2 5 Case #3 4 Case #4 105 Case #5 27 Case #6 131 Case #7 36 Case #8 109 Case #9 132 Case #10 108 Case #11 114 Case #12 84 Case #13 146 Case #14 167 Case #15 119 Case #16 41 Case #17 170 Case #18 133 Case #19 5 Case #20 19 Case #21 92 Case #22 131 Case #23 13 Case #24 83 Case #25 14 Case #26 153 Case #27 89 Case #28 26 Case #29 42 Case #30 261 Case #31 91 Case #32 37 Case #33 221 Case #34 232 Case #35 222 Case #36 344 Case #37 119 Case #38 65 Case #39 242 Case #40 37 Case #41 42 Case #42 104 Case #43 189 Case #44 184 Case #45 324 Case #46 317 Case #47 179 Case #48 128 Case #49 108 Case #50 30 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 #include <iostream> using namespace std; int result, n, m; bool visit[1001][1001]; int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; int head, tail; int arr[1000001][3]; void push_back(int x, int y, int count){ arr[tail][0] = x; arr[tail][1] = y; arr[tail][2] = count; tail++; } void pop(){ head++; } bool isEmpty(){ return head == tail; } int getTopX(){ if(!isEmpty()) return arr[head][0]; } int getTopY(){ if(!isEmpty()) return arr[head][1]; } int getTopCount(){ if(!isEmpty()) return arr[head][2]; } int main() { freopen("input.txt", "r", stdin); int T; cin >> T; for(int tc = 1; tc <= T; tc++) { head = 0, tail = 0; cin >> n >> m; int x1, y1, x2, y2; cin >> x1 >> y1; cin >> x2 >> y2; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++) visit[i][j] = false; } push_back(x1, y1, 0); visit[x1][y1] = true; while(!isEmpty()){ int x = getTopX(); int y = getTopY(); int c = getTopCount(); if(x == x2 && y == y2){ result = c; break; } pop(); for(int i = 0; i < 8; i++){ int X = x + dx[i]; int Y = y + dy[i]; if(X > 0 && X <= n && Y > 0 && Y <= m && visit[X][Y] == false){ visit[X][Y] = true; push_back(X, Y, c + 1); } } } // Output cout << "Case #" << tc << endl << result << endl; } return 0; }
Leave a Comment