Posted on 2014-01-17 18:16
Uriel 阅读(239)
评论(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 };