Capture Knight

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;
}