Untitled

mail@pastecode.io avatar
unknown
java
16 days ago
2.4 kB
2
Indexable
Never
import java.io.*;
import java.util.*;

public class Main {
    static int[] di = {-1, 1, 0, 0};
    static int[] dj = {0, 0, -1, 1};
    static void dfs(int[][] grid, int i, int j, int d, int[][] days, int n) {
        if (i == -1 || i == n || j == -1 || j == n
            || grid[i][j] == 0 || grid[i][j] == 2 || days[i][j] <= d) {
            return;
        }

        days[i][j] = d;
        for (int k = 0; k < 4; k++) {
            dfs(grid, i + di[k], j + dj[k], d + 1, days, n);
        }
    }
    public static void main(String[] args)throws IOException {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Main. */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(br.readLine());

            int[][] grid = new int[n][n];
            int[][] days = new int[n][n];
            for (int i = 0; i < n; i++) {
                String inp = br.readLine();
                for (int j = 0; j < n; j++) {
                    grid[i][j] = (int)(inp.charAt(j)) - '0';
                    days[i][j] = Integer.MAX_VALUE;
                }
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 2) {
                        for (int k = 0; k < 4; k++) {
                            dfs(grid, i + di[k], j + dj[k], 1, days, n);
                        }
                    }
                }
            }

            int minDays = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (days[i][j] == Integer.MAX_VALUE) {
                        if (grid[i][j] == 1) {
                            minDays = -1;
                            break;
                        }
                    } else {
                        minDays = Math.max(minDays, days[i][j]);
                    }
                }
                if (minDays == -1) {
                    break;
                }
            }
            if (minDays == Integer.MIN_VALUE) {
                minDays = 0;
            }
            bw.write(minDays + "\n");
        }
        bw.close();
    }
}
Leave a Comment