Untitled
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