問題文:

' x 'と' o 'を含んでいるM x Nマトリックス板を与えられて、' x 'によって4方向に囲まれるすべての領域を捕えてください.
領域は、その囲まれた地域の' X 'にすべての' O 'をひっくり返すことによって捕らえられます.

テストケース

制約

M = =ボード.長さ
n == board [ i ]です.長さ
1 <= m , n <= 200
ボード[ i ] [ j ]は' x 'または' o 'です.

アプローチ

主なことは、我々は単にXに囲まれた地域は、ボードの境界上の任意の';O ';は';X ';に反転されていないことを意味する境界線上にすべきではないすべてのOを反転することはできません注意してください.境界にない' O 'は' O 'の境界線に接続されていない' X 'に反転されます.隣接するセルが水平または垂直に接続されている場合、2つのセルが接続される.
したがって、私たちは、一番上の行、一番下の行、左のほとんどのコラムまたは最も大部分のコラムの上で4つの境界IEの上にあるそれらのOに関係しています.
これにより、マトリックスの境界にあるOを最初に見つけ、OからのDFS/BFSを行い、接続されている他のOを見つけることができます.私たちは、通常、マトリックスを横断して、これらのOとのどんな接続も持っていないそれらのOからXだけを変えます.
例えば、
x o x
x o x
x o x
この例を考えてみましょう.それで、私たちは、Oが一番上にあるセルを見つけて、DFSかBFSのどちらかをします.一方、他の文字に一時的にOを変更する検索を行うには'+'と答えます.
したがって、DFS/BFSの後、結果として生じる行列は以下のようになります.
X + X
X + X
X + X
今、私たちは通常のマトリックス横断を行います、そして、我々がマトリックスにOを見るならば、それがoに変換されるならば、我々が『+』を見るならば、彼らがXにひっくり返される規則に違反していることを意味しますので、我々はそれをOとして保ちます.
x o x
x o x
x o x
別の例を考えてみましょう.
x x x x
x o o x
x x o x
x o x x
我々は境界にあるそれらのOをチェックします.一番下の行(3、1)の境界にある1つのOがあります.DFS/BFSを行い、一時的に'+'として変更します.
x x x x
x o o x
x x o x
X + X
前に述べたように、通常の行列横断を行い、Oが存在するかどうかを確認します.もしOが存在しているなら、Xに反転してください.
x x x x
x x x x
x x x x
x o x x

コード

DFSアプローチ

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0)
            return;
        if (board.length < 3 || board[0].length < 3)
            return;
        int row = board.length;
        int col = board[0].length;
        for (int i=0; i<row; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][col - 1] == 'O') {
                dfs(board, i, col-1);
            }
        }
        for (int j=0; j<col; j++) {
            if (board[0][j] == 'O') {
                dfs(board, 0, j);
            }
            if (board[row-1][j] == 'O') {
                dfs(board, row-1, j);
            }
        }
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (board[i][j] == '+') {
                    board[i][j] = 'O';
                }
                else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void dfs(char [][] board, int i, int j) {
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != 'O')
            return;
        board[i][j] = '+';
        dfs(board, i+1, j);
        dfs(board, i-1, j);
        dfs(board, i, j-1);
        dfs(board, i, j+1);
    }
}

BFSアプローチ

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0)
            return;
        int row = board.length;
        int col = board[0].length;
        Queue<int[]> queue = new LinkedList<>();
        // add all the edge on top left right botom to queue
       for (int i=0; i<row; i++) {
           if (board[i][0] == 'O') {
               board[i][0] = '+';
               queue.offer(new int []{i, 0});
           }
           if (board[i][col - 1] == 'O') {
               board[i][col - 1] = '+';
               queue.offer(new int []{i, col - 1});
           }
       }
        for (int i=0; i<col; i++) {
            if (board[0][i] == 'O') {
                board[0][i] = '+';
                queue.offer(new int [] {0, i});
            }
            if (board[row - 1][i] == 'O') {
                board[row - 1][i] = '+';
                queue.offer(new int [] {row - 1, i});
            }
        }
        bfs(queue, row, col, board);
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (board[i][j] == '+') {
                    board[i][j] = 'O';
                }
                else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }

    }

    public void bfs(Queue<int[]> queue, int row, int col, char [][] board) {
        final int [][] directions = new int [][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
        while (!queue.isEmpty()) {
            int [] currentPos = queue.poll();
            int x = currentPos[0];
            int y = currentPos[1];
            for (int [] dir : directions) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                if (newX < 0 || newY < 0 || newX >= row || newY >= col || board[newX][newY] != 'O')
                    continue;
                board[newX][newY] = '+';
                queue.offer(new int [] {newX, newY});
            }
        }
    }
}

時間複雑性と空間複雑性

時間複雑度= O ( row * col )
空間複雑度= O ( row * col )

Rohithv 07 / LeetCode

解決されるleetcode問題。

LeetCode

解決されるleetcode問題.
View on GitHub