Untitled

mail@pastecode.io avatar
unknown
plain_text
10 months ago
2.2 kB
2
Indexable
Never
package Practice;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Mario_Climb {
	static int n, m, arr[][], visit[][], front, rear, x, y;
	static Position dat[] = new Position[1000005];

	static void reset() {
		front = rear;
	}

	static void push(Position val) {
		dat[++front] = val;
	}

	static Position pop() {
		return dat[++rear];
	}

	static boolean isE() {
		return front == rear;
	}

	static void resetV() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {

				visit[i][j] = 0;
			}
		}
	}

	static int bfs(int k) {
		reset();
		resetV();
		Position position = new Position(x, y);
		push(position);
		visit[x][y] = 1;
		int spinx[] = new int[k * 4];
		int spiny[] = new int[k * 4];
		spinx[0] = spinx[1] = 0;
		spiny[0] = 1;
		spiny[1] = -1;
		int count = 2;
		int num = 1;
		for (int i = 0; i < k; i++) {
			spinx[count] = num;
			spinx[count + 1] = -num;
			count += 2;
			num++;
		}
		while (!isE()) {
			position = pop();
			int cr = position.x;
			int cc = position.y;
			for (int i = 0; i < count; i++) {
				int nr = cr + spinx[i];
				int nc = cc + spiny[i];
				if (nr >= 0 && nr < n && nc >= 0 && nc < m && arr[nr][nc] != 0
						&& visit[nr][nc] == 0) {
					position = new Position(nr, nc);
					push(position);
					visit[nr][nc] = 1;
					if (arr[nr][nc] == 3) {
						return k;
					}
				}
			}

		}

		return -1;
	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("Text"));
		Scanner scanner = new Scanner(System.in);
		int tc = scanner.nextInt();
		for (int Case = 1; Case <= tc; Case++) {
			n = scanner.nextInt();
			m = scanner.nextInt();
			arr = new int[n][m];
			visit = new int[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					arr[i][j] = scanner.nextInt();
					if (arr[i][j] == 2) {
						x = i;
						y = j;
					}
				}
			}
			int ans = 0;
			for (int i = 1; i < n; i++) {
				if (bfs(i) != -1) {
					ans = i;
					break;
				}
			}
			System.out.println("Case #" + Case);
			System.out.println(ans);
		}

	}
}
Leave a Comment