Find shortest safe route in a matrix

//Find shortest safe route in a matrix

import java.io.*;
import java.util.*;

class IntArray {
    public static int[] input(BufferedReader br, int n) throws IOException {
        String[] s = br.readLine().trim().split(" ");
        int[] a = new int[n];

        for(int i = 0; i < n; i++) {
          a[i] = Integer.parseInt(s[i]);
        }

        return a;
    }

    public static void print(int[] a) {
        for(int e: a) {
          System.out.print(e + " ");
        }
        System.out.println();
    }

    public static void print(ArrayList<Integer> a) {
        for(int e: a) {
          System.out.print(e + " ");
        }
        System.out.println();
    }
}

class IntMatrix {
    public static int[][] input(BufferedReader br, int n, int m) throws IOException {
        int[][] mat = new int[n][];

        for(int i = 0; i < n; i++) {
            String[] s = br.readLine().trim().split(" ");
            mat[i] = new int[s.length];

            for(int j = 0; j < s.length; j++) {
              mat[i][j] = Integer.parseInt(s[j]);
            }
        }

        return mat;
    }

    public static void print(int[][] m) {
        for(var a: m) {
            for(int e: a) {
              System.out.print(e + " ");
            }
            System.out.println();
        }
    }

    public static void print(ArrayList<ArrayList<Integer>> m) {
        for(var a: m) {
            for(int e: a) {
              System.out.print(e + " ");
            }
            System.out.println();
        }
    }
}

class GFG {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t;
        t = Integer.parseInt(br.readLine());

        while(t-- > 0) {
            int[] a = IntArray.input(br, 2);
            int[][] mat = IntMatrix.input(br, a[0], a[1]);
            Solution obj = new Solution();
            int res = obj.findShortestPath(mat);
            System.out.println(res);
        }
    }
}

class Solution {
    public static int findShortestPath(int[][] mat) {
        for(int i = 0; i < mat.length; i++) {
            for(int j = 0; j < mat[0].length; j++) {
                if(mat[i][j] == 0) {
                    mat[i][j] = -1;
                    if(i - 1 >= 0 && mat[i - 1][j] == 1) {
                      mat[i - 1][j] = -1;
                    }

                    if(j - 1 >= 0 && mat[i][j - 1] == 1) {
                      mat[i][j - 1] = -1;
                    }

                    if(i + 1 < mat.length && mat[i + 1][j] == 1) {
                      mat[i + 1][j] = -1;
                    }

                    if(j + 1 < mat[0].length && mat[i][j + 1] == 1) {
                      mat[i][j + 1] = -1;
                    }
                }
            }
        }

        for(int j = mat[0].length - 2; j >= 0; j--) {
            for(int i = 0; i < mat.length; i++) {
                if(mat[i][j] == -1) {
                  continue;
                }

                if(mat[i][j + 1] == -1 || mat[i][j + 1] == 0) {
                  mat[i][j] = 0;
                }

                else {
                  mat[i][j] = mat[i][j + 1] + 1;
                }
            }

            for(int i = 0; i < mat.length; i++) {
                if(mat[i][j] == -1) {
                  continue;
                }

                if(i - 1 >= 0 && mat[i - 1][j] > 0 && (mat[i][j] == 0 || mat[i][j] > mat[i - 1][j] + 1)) {
                  mat[i][j] = mat[i - 1][j] + 1;
                }

                if(i + 1 < mat.length && mat[i + 1][j] > 0 && (mat[i][j] == 0 || mat[i][j] > mat[i + 1][j] + 1)) {
                  mat[i][j] = mat[i + 1][j] + 1;
                }
            }

            for(int i = mat.length - 1; i >= 0; i--) {
                if(mat[i][j] == -1) {
                  continue;
                }

                if(i - 1 >= 0 && mat[i - 1][j] > 0 && (mat[i][j] == 0 || mat[i][j] > mat[i - 1][j] + 1)) {
                  mat[i][j] = mat[i - 1][j] + 1;
                }

                if(i + 1 < mat.length && mat[i + 1][j] > 0 && (mat[i][j] == 0 || mat[i][j] > mat[i + 1][j] + 1)) {
                  mat[i][j] = mat[i + 1][j] + 1;
                }
            }
        }

        int min = Integer.MAX_VALUE;

        for(int a[]: mat) {
            if(a[0] > 0) {
              min = Math.min(a[0], min);
            }
        }

        if(min == 0 || min == Integer.MAX_VALUE) {
            min = -1;
        }

        return min;        
    }
}