做的想吐血的一題，交了33次才過(guò)，創(chuàng)紀(jì)錄了...
題目很簡(jiǎn)單，就是一個(gè)字符陣，由X和O構(gòu)成，找出所有O構(gòu)成的連通區(qū)域，若該區(qū)域所有O都在字符陣內(nèi)部(不在邊界上)，則把該連通區(qū)域所有O都換成X，其余不變
這題一看到就想著怎么這么裸的DFS，于是想也沒(méi)想敲完直接RE，看RE返回的是空數(shù)據(jù)，于是加了判board為空的語(yǔ)句，交上去還是RE，因?yàn)橹白鯨eetCode這種RE的情況都是沒(méi)有判空，于是換了N種寫法判空，還是RE
因?yàn)槭情_(kāi)了個(gè)數(shù)組記錄字符陣每個(gè)元素是否訪問(wèn)過(guò)，又開(kāi)了另一個(gè)數(shù)組判該連通區(qū)域是否鄰邊，想著是不是數(shù)組開(kāi)太大了，于是試了各種數(shù)組大小，發(fā)現(xiàn)開(kāi)bool型，只開(kāi)一個(gè)數(shù)組能過(guò)，后來(lái)想到其實(shí)不需要另開(kāi)一個(gè)數(shù)組記錄是否鄰邊，搜的時(shí)候只搜四邊上為O的那些位置，這樣一定是鄰邊的，這個(gè)時(shí)間復(fù)雜度也小一些，于是改了，還是RE，而且掛在大數(shù)據(jù)上，但是我并沒(méi)有開(kāi)數(shù)組，不會(huì)有越界發(fā)生，然后就各種吐血的改來(lái)改去，終于AC，雖然還是很莫名...為啥之前會(huì)報(bào)RE呢？
這是AC的代碼：
1 class Solution {
2 public:
3 void DFS(int x, int y, vector<vector<char>> &board) {
4 int tx, ty;
5 if(x >= board.size() || y >= board[0].size() || x < 0 || y < 0 || board[x][y] != 'O') return;
6 board[x][y] = 'Q';
7 DFS(x, y + 1, board);
8 DFS(x, y - 1, board);
9 DFS(x + 1, y, board);
10 DFS(x - 1, y, board);
11 }
12
13 void solve(vector<vector<char>> &board) {
14 if(board.empty()) return;
15 int row = board.size();
16 if(!row) return;
17 int col = board[0].size();
18 if(!col) return;
19 for(int i = 0; i < row; ++i) {
20 if(board[i][0] == 'O') DFS(i, 0, board);
21 if(board[i][col - 1] == 'O') DFS(i, col - 1, board);
22 }
23 for(int i = 0; i < col; ++i) {
24 if(board[0][i] == 'O') DFS(0, i, board);
25 if(board[row - 1][i] == 'O') DFS(row - 1, i, board);
26 }
27 for(int i = 0 ; i < row; ++i) {
28 for(int j = 0; j < col; ++j) {
29 if(board[i][j] == 'Q') board[i][j] = 'O';
30 else if(board[i][j] == 'O') board[i][j] = 'X';
31 }
32 }
33 }
34
35 };