Untitled
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...