01 Matrix

class Pair{
    public int i;
    public int j;
    public Pair(int x, int y){
        i = x;
        j = y;
    }
}
class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {-1, 1, 0, 0};
    public int[][] updateMatrix(int[][] matrix) {
        int[][] res = new int[matrix.length][matrix[0].length];
        for(int i = 0; i<matrix.length; i++){
            for(int j = 0; j<matrix[0].length; j++){
                res[i][j] = bfs(matrix, i, j);
            }
        }
        return res;
    }
    public int bfs(int[][] matrix, int start, int starty){
        Queue<Pair> q = new LinkedList<>();
        Pair first = new Pair(start, starty);
        int dist = 0;
        q.add(first);
        while(!q.isEmpty()){
            int s = q.size();
            for(int i = 0; i<s; i++){
                Pair cur = q.poll();
                if(matrix[cur.i][cur.j] == 0){
                    dist = Math.abs(start - cur.i) + Math.abs(starty - cur.j);
                    return dist;
                }
                for(int j = 0; j<4; j++){
                    int newi = cur.i + dx[j];
                    int newj = cur.j + dy[j];
                    if(newi >= 0 && newi < matrix.length && newj >= 0 && newj < matrix[0].length){
                        Pair newp = new Pair(newi, newj);
                        q.add(newp);
                    }
                }
            }
        }
        return -1;
    }
}