Untitled

 avatar
unknown
plain_text
2 years ago
3.2 kB
3
Indexable
package practise;

import java.util.Scanner;

class MyStack{
	private int max, top;
	private int[] arr;
	
	public MyStack(int len) {
		// TODO Auto-generated constructor stub
		max = len;
		top = -1;
		arr = new int[max];
	}
	
	public void push(int val) {
		arr[++top] = val;
	}
	
	public int pop() {
		return arr[top--];
	}
	
	public boolean isEmpty() {
		return top == -1;
	}
	
}

public class mario_climbing {
	static int row, col, minJ;
	static int sx, sy, ex, ey;
	static int[][] map, d = {{-1, 0, 1, 0}, {0, 1, 0, -1}};
	static boolean[][] visit;
	static MyStack qx, qy;
	
	private static void jump(int x, int y, int h) {
		if(x == ex && y == ey) {
			minJ = h < minJ ? h : minJ;
			return;
		}
		
		if(minJ < h) return;
		
		int dx, dy; boolean flag;
		for(int i = 0; i < 4; i++) {
			if(i % 2 == 0) {
				int k = 1;
				dy = y;
				dx = x + k * d[0][i];
				flag = false;
				while(dx >= 0 && dy >= 0 && dx < row && dy < col) {
					if(!visit[dx][dy] && map[dx][dy] != 0) {
						flag = true;
						break;
					}
					k++;
					dx = x + k * d[0][i]; dy = y + k * d[1][i];
				}
				
				if(flag) {
					visit[dx][dy] = true;
					if(h < k) jump(dx, dy, k);
					else jump(dx, dy, h);
					visit[dx][dy] = false;
				}
				
			}
			else {
				dx = x + d[0][i]; dy = y +  d[1][i];
				if(dx >= 0 && dy >= 0 && dx < row && dy < col && !visit[dx][dy] && map[dx][dy] != 0) {
					visit[dx][dy] = true;
					jump(dx, dy, h);
					visit[dx][dy] = false;
				}
			}
		}
		
	}
	
	private static boolean jump2() {
		reset();
		qx = new MyStack(row * col);
		qy = new MyStack(row * col);
		int x, y, dx, dy;
		qx.push(sx); qy.push(sy);
		visit[sx][sy] = true;
		
		while(!qx.isEmpty()) {
			x = qx.pop(); y = qy.pop();
			for(int i = 0; i < 4; i++) {
				dy = y + d[1][i];
				if(dy >= 0 && dy < col) {
					for(int j = 1; j <= minJ; j++) {
						dx = x + j * d[0][i];
						if(dx >= 0 && dx < row && map[dx][dy] != 0 && !visit[dx][dy]) {
							if(dx == ex && dy == ey) return true;
							qx.push(dx); qy.push(dy);
							visit[dx][dy] = true;
						}
					}
				}
			}
		}
		return false;
	}
	
	private static void reset() {
		for(int i = 0; i < row; i++) {
			for(int j = 0; j < col; j++) {
				visit[i][j] = false;
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int tc = 1; tc <= testcase; tc++) {
			row = sc.nextInt(); col = sc.nextInt();
			map = new int[row][col];
			visit = new boolean[row][col];
			for(int i = 0; i < row; i++) {
				for(int j = 0; j < col; j++) {
					map[i][j] = sc.nextInt();
					if(map[i][j] == 2) {
						sx = i; sy = j;
					}
					else if(map[i][j] == 3) {
						ex = i; ey = j;
					}
				}
			}
			
//			minJ = Integer.MAX_VALUE;
//			visit[sx][sy] = true;

//			qx = new MyStack(row * col);
//			qy = new MyStack(row * col);
			minJ = 1;
			while(!jump2()) {
				minJ++;
			}
			
			System.out.println("Case #" + tc);
			System.out.println(minJ);
			
		}
	}

}
Editor is loading...