蜜桃在线无码,欧美A区,亚洲波多野结衣,国产淫伦久久久久久久,婷婷五月欧美乱伦,亚洲视频一区二区在线,一级黄色电影在线播放,国产精品―色哟呦

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?被圍繞的區(qū)域，我們先來看題面：

https://leetcode-cn.com/problems/surrounded-regions/

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

題意

給定一個二維的矩陣，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 圍繞的區(qū)域，并將這些區(qū)域里所有的 'O' 用 'X' 填充。

樣例


示例:

X X X X
X O O X
X X O X
X O X X

運(yùn)行你的函數(shù)后，矩陣變?yōu)椋?br mpa-from-tpl="t">
X X X X
X X X X
X X X X
X O X X

解釋:

被圍繞的區(qū)間不會存在于邊界上，
換句話說，任何邊界上的?'O'?都不會被填充為?'X'。任何不在邊界上，
或不與邊界上的?'O'?相連的?'O'?最終都會被填充為?'X'。
如果兩個元素在水平或垂直方向相鄰，則稱它們是“相連”的。

解題

從邊界出發(fā)把,先把邊界上和O連通點(diǎn)找到, 把這些變成B,然后遍歷整個board把O變成X, 把B變成O

如下圖所示

思路一: DFS

class?Solution?{
????int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

????public?void?solve(char[][] board) {
????????if?(board == null?|| board.length == 0?|| board[0] == null?|| board[0].length == 0) return;
????????int?row = board.length;
????????int?col = board[0].length;
????????for?(int?j = 0; j < col; j++) {
????????????// 第一行
????????????if?(board[0][j] == 'O') dfs(0, j, board, row, col);
????????????// 最后一行
????????????if?(board[row - 1][j] == 'O') dfs(row - 1, j, board, row, col);
????????}

????????for?(int?i = 0; i < row; i++) {
????????????// 第一列
????????????if?(board[i][0] == 'O') dfs(i, 0, board, row, col);
????????????// 最后一列
????????????if?(board[i][col - 1] == 'O') dfs(i, col - 1, board, row, col);
????????}

????????// 轉(zhuǎn)變
????????for?(int?i = 0; i < row; i++) {
????????????for?(int?j = 0; j < col; j++) {
????????????????if?(board[i][j] == 'O') board[i][j] = 'X';
????????????????if?(board[i][j] == 'B') board[i][j] = 'O';
????????????}
????????}

????}

????private?void?dfs(int?i, int?j, char[][] board, int?row, int?col) {
????????board[i][j] = 'B';
????????for?(int[] dir : dirs) {
????????????int?tmp_i = dir[0] + i;
????????????int?tmp_j = dir[1] + j;
????????????if?(tmp_i < 0?|| tmp_i >= row || tmp_j < 0?|| tmp_j >= col || board[tmp_i][tmp_j] != 'O') continue;
????????????dfs(tmp_i, tmp_j, board, row, col);
????????}
????}
}

思路二: BFS

class?Solution?{
????int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
????private?static?class?Point?{
????????int?x, y;

????????Point(int?x, int?y) {
????????????this.x = x;
????????????this.y = y;
????????}
????}

????public?void?solve(char[][] board)?{
????????if?(board == null || board.length == 0?|| board[0] == null || board[0].length == 0) return;
????????int?row = board.length;
????????int?col = board[0].length;
????????for?(int?j = 0; j < col; j++) {
????????????// 第一行
????????????if?(board[0][j] == 'O') bfs(0, j, board, row, col);
????????????// 最后一行
????????????if?(board[row - 1][j] == 'O') bfs(row - 1, j, board, row, col);
????????}

????????for?(int?i = 0; i < row; i++) {
????????????// 第一列
????????????if?(board[i][0] == 'O') bfs(i, 0, board, row, col);
????????????// 最后一列
????????????if?(board[i][col - 1] == 'O') bfs(i, col - 1, board, row, col);
????????}

????????// 轉(zhuǎn)變
????????for?(int?i = 0; i < row; i++) {
????????????for?(int?j = 0; j < col; j++) {
????????????????if?(board[i][j] == 'O') board[i][j] = 'X';
????????????????if?(board[i][j] == 'B') board[i][j] = 'O';
????????????}
????????}

????}

????private?void?bfs(int?i, int?j, char[][] board, int?row, int?col)?{
????????Deque queue?= new?LinkedList<>();
????????queue.offer(new?Point(i, j));
????????while?(!queue.isEmpty()) {
????????????Point tmp = queue.poll();
????????????if?(tmp.x >= 0?&& tmp.x < row && tmp.y >= 0?&& tmp.y < col && board[tmp.x][tmp.y] == 'O') {
????????????????board[tmp.x][tmp.y] = 'B';
????????????????for?(int[] dir : dirs) queue.offer(new?Point(tmp.x + dir[0], tmp.y + dir[1]));
????????????}
????????}
????}
}