Accepted 12 ms Java Solution


  • 0
    A
    class GridPoint {
    
      int i;
      int j;
      int val;
    
      public GridPoint(int i, int j, int val) {
        super();
        this.i = i;
        this.j = j;
        this.val = val;
      }
    
    }
    
     public static int shortestDistance(int[][] g) {
        int i = 0;
        int j = 0;
        int m = g.length;
        int c = 1;
        int n = g[0].length;
        int[][] vis = new int[m][n];
        for (i = 0; i < m; i++) {
          for (j = 0; j < n; j++) {
            g[i][j] = -1 * g[i][j];
            vis[i][j] = 0;
          }
        }
    
        for (i = 0; i < m; i++) {
          for (j = 0; j < n; j++) {
            if (g[i][j] == -1) {
              bfs(g, i, j, 1, m, n, c, vis);
              checkIfCountSame(c, vis, g);
              c += 1;
            }
          }
        }
        int ans = 999999;
        for (i = 0; i < m; i++) {
          for (j = 0; j < n; j++) {
            if (g[i][j] > 0) {
              ans = Math.min(ans, g[i][j]);
            }
          }
        }
        if (ans == 999999)
          return -1;
        return ans;
    
      }
    
      private static void checkIfCountSame(int c, int[][] vis, int[][] g) {
        int i, j;
        int m = g.length;
        int n = g[0].length;
        for (i = 0; i < m; i++) {
          for (j = 0; j < n; j++) {
            if (g[i][j] >= 0) {
              if (vis[i][j] != c) {
                // not reachable from here
                g[i][j] = -2;
              }
            }
          }
        }
    
      }
    
      private static void bfs(int[][] g, int i, int j, int val, int m, int n, int c, int[][] vis) {
        LinkedList<GridPoint> q = new LinkedList<GridPoint>();
        q.add(new GridPoint(i, j, val));
        while ( !q.isEmpty()) {
          GridPoint p = q.poll();
          bfsHelper(g, p.i, p.j, p.val, m, n, vis, c, q);
        }
      }
    
      private static void bfsHelper(int[][] g, int i, int j, int val, int m, int n, int[][] vis, int count,
                                    LinkedList<GridPoint> q) {
        int[] dx = { -1, 1, 0, 0 };
        int[] dy = { 0, 0, -1, 1 };
        for (int k = 0; k < 4; k++) {
          int x = i + dx[k];
          int y = j + dy[k];
          if (inBound(x, y, m, n) && g[x][y] >= 0 && vis[x][y] != count) {
            g[x][y] += val;
            q.add(new GridPoint(x, y, val + 1));
            vis[x][y] = count;
          }
        }
    
      }
    
      private static boolean inBound(int x, int y, int m, int n) {
    
        return (x >= 0 && y >= 0 && x < m && y < n);
      }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.