Mario Climb

Level 4
Mario Climb


Mario cần phải di chuyển từ vị trí có giá trị bằng 2 và ăn vàng ở ô có giá trị bằng 3

0 là nhữngô Mario không thể qua

1 là nhữngô Mario có thể qua

2 là vị trícủa Mario

3 là vị trí Mario cần di chuyển đến

Các vị trí này được thể hiện bằng ma trận NxM( 2<=N,M<=50)

Mario có thểdi chuyển theo hàng ngang hoặc hàng dọc

Hàng ngang mario chỉ nhảy được tối đa 1 bước

Hàng dọc mario có thể nhảy được “h” bước

Tìm bước nhảy “h” tối thiểu để Mario có thể ăn được vàng

Sample Input

3

5 8
1 1 1 1 0 0 0 0
0 0 0 3 0 1 1 1
1 1 1 0 0 1 0 0
0 0 0 0 0 0 1 0
2 1 1 1 1 1 1 1

5 6
0 1 1 1 0 0
3 1 0 1 1 0
0 0 0 0 1 1
0 0 0 0 0 1
2 1 1 1 1 1

9 13
0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 1 3
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 1 1 1 1 1 1 1 1 1 1 1

Sample output

Case #1
2
Case #2
1
Case #3
3

Case #1
2
Case #2
1
Case #3
3
Case #4
1
Case #5
3
Case #6
6
Case #7
3
Case #8
8
Case #9
5
Case #10
7
Case #11
9
Case #12
4
Case #13
11
Case #14
6
Case #15
10
Case #16
10
Case #17
5
Case #18
7
Case #19
5
Case #20
11
Case #21
6
Case #22
22
Case #23
5
Case #24
7
Case #25
9
Case #26
3
Case #27
2
Case #28
7
Case #29
4
Case #30
5
Case #31
9
Case #32
9
Case #33
5
Case #34
7
Case #35
9
Case #36
20
Case #37
5
Case #38
12
Case #39
12
Case #40
8
Case #41
8
Case #42
22
Case #43
11
Case #44
8
Case #45
2
Case #46
10
Case #47
5
Case #48
18
Case #49
49
Case #50
49
Time: 0.56300 s.

#include <iostream>
#include <time.h>
using namespace std;

int oo = 2000000000;

int T, n, m, mp[51][51], vs[51][51]; 
int xStart, yStart, xStop, yStop, result;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int dm[4] = {1, 1, 1, 1};

bool inSize(int x, int y){
	return x >= 0 && y >= 0 && x < n & y < m;
}

void resetVs(){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++) vs[i][j] = 0;
	}
}

void backtrack(int x, int y){
	if(vs[xStop][yStop]) return;

	for(int d = 0; d < 4; d++){
		for(int dd = 1; dd <= dm[d]; dd++){
			int xx = x + dx[d]*dd;
			int yy = y + dy[d]*dd;
			if(inSize(xx, yy) && !vs[xx][yy] && mp[xx][yy] != 0){
				vs[xx][yy]++;
				backtrack(xx, yy);
			}
		}
	}
}

int main(){

	freopen("input.txt", "r", stdin);

	// Calc clock
	clock_t time_start, time_end; 
	time_start = clock(); 
	
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		// Initial && Input
		result = 0;
		cin >> n >> m;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				cin >> mp[i][j];
				if(mp[i][j] == 2) xStart = i, yStart = j;
				else if(mp[i][j] == 3) xStop = i, yStop = j;
			}
		}

		// Solve Problem 
		for(int h = 1; h <= n - 1; h++){
			resetVs();
			vs[xStart][yStart]++;
			dm[0] = h, dm[1] = h;
			backtrack(xStart, yStart);

			if(vs[xStop][yStop]){
				result = h;
				break;
			}
		}

		// Output
		cout << "Case #" << tc << "\n" << result << endl;
	}

	// Calc Time
	time_end = clock();
	cout.setf(ios::fixed);
	cout.precision(5);
	cout << "Time: " << double (time_end - time_start) / double (CLOCKS_PER_SEC) << " s." << endl;
	
	return 0;
 }