Untitled

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





Code:
#include<iostream>
#define max 1000000
using namespace std;
int n,m;
int queue[2][1000];
int front =-1 ;
int rear=-1;
int map[60][60];
int visit[60][60];
int Si, Sj, Ei, Ej;
int di[4]={0, 0, 1, -1};
int dj[4]={1,-1, 0, 0};
int ans; 

void push(int i, int j){
	if(rear == max-1) rear =-1;
	rear++;
	queue[0][rear]=i;
	queue[1][rear]=j;
}
void pop(){
	if(front == max-1) front =-1;
	front++;
}
bool IsEmpty(){
	return front == rear;
}

bool checkIn(int i, int j){
	if(i>=0 && i < n && j>=0 && j < m) return true;
	return false;
}
void reset(){
	front = -1;
	rear = -1;
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			visit[i][j] = 0;
		}
	}
}
bool bfs(int h, int i, int j){
	reset();
	push(i,j);
	visit[i][j] =1;
	while(!IsEmpty()){
		pop();
		int i1=queue[0][front];
		int j1 = queue[1][front];		
		for(int i=0; i<4; i++){
			for(int k=1; k<=h; k++){ 
				int i2= i1 + k*di[i];
				int j2 = j1 + dj[i];
				if(checkIn(i2,j2) && visit[i2][j2] == 0 && map[i2][j2] == 1 ){
					visit[i2][j2] =1;
					push(i2,j2);
				}
				if(checkIn(i2,j2)&& visit[i2][j2] == 0 && map[i2][j2] == 3){
					return true;
				}
			}
		}
	}
	return false;
}


int main(){
	freopen("text.txt", "r", stdin);

	int test; 
	cin >> test;
	for(int tc =1; tc <= test; tc++){
		cin >> n >> m;
		for(int i=0; i < n;i++){
			for(int j=0; j < m; j++){
				cin >> map[i][j];
				if(map[i][j] == 2){
					Si=i;
					Sj=j;
				}
			}
		}
		ans=0;
		for(int h=1; h <= n-1; h++){
			if(bfs(h, Si, Sj) ==true){
				ans = h;
				break;
			}
		}
		cout << "Case #" << tc << endl;
		cout << ans << endl;
	}
	return 0;
}