Untitled

 avatar
user_9638001
plain_text
7 months ago
1.8 kB
4
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;


public class MarioClimb {
	static int map[][] = new int[101][101];
	static int visit[][] = new int[101][101];
	static int ans, n,m,c,d,f=-1,r=-1, turn;
	static int[] Qx = new int[1000001];
	static int[] Qy = new int[1000001];
	static boolean check;
	
	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc =  new Scanner(System.in);
		int test = sc.nextInt();
		for(int tc = 1; tc <= test; tc++){
			ans = 0;
			check = false;
			n = sc.nextInt();
			m = sc.nextInt();
			for(int i = 0; i<n; i++){
				for(int j = 0; j<m; j++){
					map[i][j] = sc.nextInt();
					if(map[i][j] == 3){
						c = i;
						d = j;
					}
				}
			}
			while(check==false){
				ans++;
				bfs();
			}
			System.out.println("Case #"+tc);
			System.out.println(ans);
		}
	}
	public static void Push(int x, int y){
		f++;
		Qx[f] = x;
		Qy[f] = y;
	}
	
	public static void Pop(int[] tmp){
		r++;
		tmp[0] = Qx[r];
		tmp[1] = Qy[r];
	}
	
	public static void enQueue(int x, int y){
		if(check==false && x>=0 && x < n && y >= 0 && y <m && visit[x][y]==0 && map[x][y] != 0){
			visit[x][y] = 1;
			Push(x,y);
			if(x == c && y == d) check = true;
		}
	}
	private static void bfs() {
		// TODO Auto-generated method stub
		int a,b;
		for(int i = 0; i<n; i++){
			for(int j = 0; j<m; j++){
				visit[i][j] = 0;
			}
		}
		f = 0; 
		r = -1;
		Qx[0] = n-1;
		Qy[0] = 0;
		while(f > r && check== false){
			int tmp[] = new int[2];
			Pop(tmp);
			a = tmp[0];
			b = tmp[1];
			enQueue(a, b-1);
			enQueue(a, b+1);
			for(int i = 1; i<=ans; i++){
				enQueue(a-i, b);
				enQueue(a+i, b);
			}
		}
	}
}
Leave a Comment