題目：130. 被圍繞的區域

思路

代碼

Method 1 : 深度優先搜索，自己寫的

class Solution {
private:int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};void dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, int x, int y){int m = board.size(), n = board[0].size();int i, j;int next_x, next_y;for(i = 0; i < 4; i++){next_x = x + dir[i][0];next_y = y + dir[i][1];if(next_x < 0 || next_x >= m || next_y < 0 || next_y >= n){continue;}if(!visited[next_x][next_y] && board[next_x][next_y] == 'O'){visited[next_x][next_y] = true;dfs(board, visited, next_x, next_y);}}}public:void solve(vector<vector<char>>& board) {int i, j;int m = board.size(), n = board[0].size();vector<vector<bool>> visited(m, vector<bool>(n, false));// 和邊界相鄰的'O'都要打上標記for(j = 0; j < n; j++){for(int i : {0, m-1})if(!visited[i][j] && board[i][j] == 'O'){visited[i][j] = true;dfs(board, visited, i, j);}}for(i = 0; i < m; i++){for(int j : {0, n-1}){if(!visited[i][j] && board[i][j] == 'O'){visited[i][j] = true;dfs(board, visited, i, j);}}}for(i = 0; i < m; i++){for(j = 0; j < n; j++){if(visited[i][j]){visited[i][j] = false;board[i][j] = 'A'; // 最后要還原為'O'}}}// 開始遍歷for(i = 0; i < m; i++){for(j = 0; j < n; j++){if(!visited[i][j] && board[i][j] == 'O'){visited[i][j] = true;dfs(board, visited, i, j);}}}for(i = 0; i < m; i++){for(j = 0; j < n; j++){if(board[i][j] == 'A'){cout << "hello !";board[i][j] = 'O'; // 最后要還原為'O'}if(visited[i][j]){board[i][j] = 'X';}}}return;}
};

先將與邊界相連的島嶼設置為A，再將剩下的島嶼設置為X，最后將剛才的A換成O；