一、題目描述

給定一個(gè)二維的矩陣，包含 ‘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)?#xff1a;

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

解釋:

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

三、分析

與邊界"O"有聯(lián)系的區(qū)域都不會(huì)填充，其他的會(huì)被填充。
==》
本題用到了深度優(yōu)先遍歷和回溯法，解題方式也是之前未見過的，方法是很巧妙的。

首先想到的是對邊界的’0’進(jìn)行標(biāo)記，與邊界’0’相連的’0’也進(jìn)行標(biāo)記，并標(biāo)記為’+’；

其次查找連續(xù)’0’的方法，采用的是深度優(yōu)先遍歷，實(shí)現(xiàn)的過程回溯法。

最后沒有被標(biāo)記的’0’即為被包圍的，將會(huì)被修改為’X’，而’+‘將被恢復(fù)為’0’。

四、實(shí)現(xiàn)

class Solution { public:void dfs(vector<vector<char>>& board, int row, int col){if(row < 0 || row >= board.size() || col < 0 || col >= board[0].size())return;if(board[row][col] != 'O')return;board[row][col] = '+';dfs(board, row + 1, col);dfs(board, row, col + 1);dfs(board, row - 1, col);dfs(board, row, col - 1);}void solve(vector<vector<char>>& board) {if(board.size() <= 1 || board[0].size() <= 2)return;for(int i = 0; i < board.size(); i ++){if(board[i][0] == 'O')dfs(board, i, 0);if(board[i][board[0].size() - 1] == 'O')dfs(board, i, board[0].size() - 1);}for(int i = 0; i < board[0].size(); i ++){if(board[0][i] == 'O')dfs(board, 0, i);if(board[board.size() - 1][i] == 'O')dfs(board, board.size() - 1, i);}// 對'+'進(jìn)行恢復(fù)，對'0'進(jìn)行修改for(int i = 0; i < board.size(); i ++){for(int j = 0; j < board[0].size(); j ++){if(board[i][j] == '+')board[i][j] = 'O';else if(board[i][j] == 'O')board[i][j] = 'X';}}} };

總結(jié)

以上是生活随笔為你收集整理的【LeetCode】130.被围绕的区域的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。