Another accepted Java solution


  • 1
    public class Solution {
      int[] dx = {-1, 1, 0, 0};
      int[] dy = {0, 0, -1, 1};
      
      public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) 
          return;
        
        int n = board.length;
        int m = board[0].length;
        
        // scan the borders and mark the 'O's to '1'
        for (int i = 0; i < n; i++)
          for (int j = 0; j < m; j++)
            if ((i * j == 0 || i == n - 1 || j == m - 1) && board[i][j] == 'O')
              bfs(board, n, m, i, j);
        
        // scan the inner area and mark the 'O's to 'X'
        for (int i = 1; i < n; i++)
          for (int j = 1; j < m; j++)
            if (board[i][j] == 'O')
              board[i][j] = 'X';
        
        // reset all the '1's to 'O's
        for (int i = 0; i < n; i++)
          for (int j = 0; j < m; j++)
            if (board[i][j] == '1')
              board[i][j] = 'O';
                      
      }
      
      void bfs(char[][] board, int n, int m, int i, int j) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(i * m + j);
        
        board[i][j] = '1';
        
        while (!queue.isEmpty()) {
          Integer pos = queue.poll();
          
          int row = pos / m;
          int col = pos % m;
            
          for (int k = 0; k < 4; k++) {
            i = row + dx[k];
            j = col + dy[k];
              
            if (i >= 0 && i < n && j >= 0 && j < m && board[i][j] == 'O') {
              board[i][j] = '1';
              queue.add(i * m + j);
            }
          }
        }
      }
    
    }

  • 0
    G

    What are you doing with nulls in the queue? It still works after removing those.


  • 0

    Hi gwang8, null tells me when the current layer is finished scanning, it's my habits of doing BFS traversal, but you are right, we don't need that here, removing will make the code cleaner! Thanks for pointing this out!


Log in to reply
 

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