Untitled

mail@pastecode.io avatarunknown
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
*/