nord vpnnord vpn
Ad

Untitled

mail@pastecode.io avatar
unknown
plain_text
21 days ago
2.0 kB
1
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, m, map[][], x, y, min, visit[][];
	static Queue queue = new Queue(100000);
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { 1, -1, 0, 0 };

	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("src/input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {
			n = sc.nextInt();
			m = sc.nextInt();
			map = new int[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					map[i][j] = sc.nextInt();
					if (map[i][j] == 2) {
						x = i;
						y = j;
					}
				}
			}
			min = -1;
			for (int i = 1; i <= n; i++) {
				visit = new int[n][m];
				if (bfs(i)) {
					min = i;
					break;
				}
			}
			System.out.println("Case #" + tc);
			System.out.println(min);
		}
		sc.close();
	}

	private static boolean bfs(int k) {
		// TODO Auto-generated method stub
		queue.reset();
		queue.push(x);
		queue.push(y);
		visit[x][y] = 1;
		int r, c;
		while (!queue.empty()) {
			r = queue.pop();
			c = queue.pop();
			for (int i = 0; i < 4; i++) {
				for (int j = 1; j <= k; j++) {
					int nr = r + dx[i] * k;
					int nc = c + dy[i];

					if (nr >= 0 && nc >= 0 && nr < n && nc < m && visit[nr][nc] == 0 && map[nr][nc] != 0) {
						visit[nr][nc] = 1;
						queue.push(nr);
						queue.push(nc);
						if (map[nr][nc] == 3)
							return true;
					}
				}
			}
		}
		return false;
	}

}

class Queue {
	static int r, f, arr[];

	Queue(int c) {
		r = f = 0;
		arr = new int[c];
	}

	boolean empty() {
		return r == f;
	}

	void reset() {
		f = r = 0;
	}

	void push(int data) {
		arr[r] = data;
		r++;
	}

	int pop() {
		f++;
		return arr[f - 1];
	}
}
Leave a Comment


nord vpnnord vpn
Ad