Posted on 2014-01-17 18:16
Uriel 閱讀(273)
評論(0) 編輯 收藏 引用 所屬分類:
LeetCode
做的想吐血的一題，交了33次才過，創紀錄了...
題目很簡單，就是一個字符陣，由X和O構成，找出所有O構成的連通區域，若該區域所有O都在字符陣內部(不在邊界上)，則把該連通區域所有O都換成X，其余不變
這題一看到就想著怎么這么裸的DFS，于是想也沒想敲完直接RE，看RE返回的是空數據，于是加了判board為空的語句，交上去還是RE，因為之前做LeetCode這種RE的情況都是沒有判空，于是換了N種寫法判空，還是RE
因為是開了個數組記錄字符陣每個元素是否訪問過，又開了另一個數組判該連通區域是否鄰邊，想著是不是數組開太大了，于是試了各種數組大小，發現開bool型，只開一個數組能過，后來想到其實不需要另開一個數組記錄是否鄰邊，搜的時候只搜四邊上為O的那些位置，這樣一定是鄰邊的，這個時間復雜度也小一些，于是改了，還是RE，而且掛在大數據上，但是我并沒有開數組，不會有越界發生，然后就各種吐血的改來改去，終于AC，雖然還是很莫名...為啥之前會報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 };