h***i
发帖数: 1970 | 1 O(n*n)怎么也过不了large test?
void solve(vector> &board) {
int m = board.size();
if (m == 0) return;
int n = board[0].size();
unordered_set checked;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'X') continue;
if (checked.find(i * n + j) != checked.end()) continue;
unordered_set s;
queue q;
s.insert(i * n + j);
q.push(i * n + j);
bool fill = true;
while (!q.empty()) {
int k = q.front();
q.pop();
int jj = k % n;
int ii = k / n;
checked.insert(ii * n + jj);
if (ii == 0 || ii == m - 1 || jj == 0 || jj == n - 1)
fill = false;
if (ii + 1 < m && board[ii+1][jj] == 'O') {
s.insert((ii + 1) * n + jj);
q.push((ii + 1) * n + jj);
}
if (jj + 1 < n && board[ii][jj+1] == 'O') {
s.insert(ii* n + jj + 1);
q.push(ii * n + jj + 1);
}
}
if (fill) {
for (unordered_set::iterator it = s.begin();
it != s.end(); ++it) {
int k = *it;
int jj = k % n;
int ii = k / n;
board[ii][jj] = 'X';
}
}
}
}
} | p*****2
发帖数: 21240 | | p****e
发帖数: 3548 | | f*******t
发帖数: 7549 | 4 什么错？
【在 p****e 的大作中提到】
: 我的也不行，怎么检查代码都出错，小数据没问题
| l***i
发帖数: 1309 | 5 judge does not like dfs, seems recursion depth is huge. Use bfs should work.
My code for reference:
class Solution {
public:
void dfs(char marker, int r, int c, vector > &board)
{
board[r][c] = marker;
int n = board.size(), m = board[0].size();
int d[][2] = {{-1,0}, {0,+1}, {+1,0}, {0,-1}};
queue > que;
que.push(make_pair(r,c));
while (!que.empty()) {
pair p = que.front(); que.pop();
int i = p.first, j = p.second;
for (int x = 0; x < 4; ++x) {
int i2, j2;
i2 = i + d[x][0]; j2 = j + d[x][1];
if (0 <= i2 && i2 < n && 0 <= j2 && j2 < m
&& board[i2][j2] == 'O') {
board[i2][j2] = marker; que.push(make_pair(i2,j2));
}
}
}
// judge does not like dfs
/*
for (int x=0; x<4; ++x) {
int i = r + d[x][0];
int j = c + d[x][1];
if (0 <= i && i < n && 0 <= j && j < m && board[i][j] == 'O') {
dfs(marker, i, j, board);
}
} */
}
void solve(vector> &board) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (board.empty()) return;
// start from border, mark all O, then set all other O to X
int n = board.size(), m = board[0].size();
const char marker = 'T';
for (int j=0; j
int i;
i = 0; if (board[i][j] == 'O') dfs(marker, i, j, board);
i = n-1; if (board[i][j] == 'O') dfs(marker, i, j, board);
}
for (int i=0; i
int j;
j = 0; if (board[i][j] == 'O') dfs(marker, i, j, board);
j = m-1; if (board[i][j] == 'O') dfs(marker, i, j, board);
}
for (int i=0; i
for (int j=0; j
if (board[i][j] == marker) board[i][j] = 'O';
else if (board[i][j] == 'O') board[i][j] = 'X';
}
}; | p*****2
发帖数: 21240 | 6
work.
LZ的不是dfs吧？我倒是在你的code里边看到dfs了。
【在 l***i 的大作中提到】
: judge does not like dfs, seems recursion depth is huge. Use bfs should work.
: My code for reference:
: class Solution {
: public:
: void dfs(char marker, int r, int c, vector > &board)
: {
: board[r][c] = marker;
: int n = board.size(), m = board[0].size();
: int d[][2] = {{-1,0}, {0,+1}, {+1,0}, {0,-1}};
: queue > que;
| h***i
发帖数: 1970 | 7 你的这个从四边往中间走的思路好，什么都不用记了。
【在 p*****2 的大作中提到】
:
: work.
: LZ的不是dfs吧？我倒是在你的code里边看到dfs了。
| h***i
发帖数: 1970 | 8 贴个旁门左道。 88 milli secs过large test.
typedef struct FU {
int parent;
bool fill;
int rank;
FU(int v, bool f)
: parent(v),
fill(f),
rank(0) {
}
} FU;
int find(int i, vector &v) {
if (v[i].parent == i) return i;
v[i].parent = find(v[i].parent, v);
return v[i].parent;
}
void union_by_rank(int i, int j, vector &v) {
int k = find(i, v);
int l = find(j, v);
if (k == l) return;
if (v[k].rank < v[l].rank) {
v[k].parent = l;
if (v[k].fill == false) v[l].fill = false;
}
else if (v[k].rank > v[l].rank) {
v[l].parent = k;
if (v[l].fill == false) v[k].fill = false;
}
else {
v[l].parent = k;
v[k].rank += 1;
if (v[l].fill == false) v[k].fill = false;
}
}
void solve(vector> &board) {
int m = board.size();
if (m == 0) return;
int n = board[0].size();
vector v;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
v.push_back(FU(i * n + j, true));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'X') continue;
int index = i * n + j;
if (i + 1 < m && board[i + 1][j] == 'O')
union_by_rank(index + n, index, v);
if (j + 1 < n && board[i][j + 1] == 'O')
union_by_rank(index, index + 1, v);
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
int l = find(index, v);
v[l].fill = false;
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'X') continue;
int l = find(i * n + j, v);
if (v[l].fill)
board[i][j] = 'X';
}
}
}
【在 h***i 的大作中提到】
: 你的这个从四边往中间走的思路好，什么都不用记了。
| w****a
发帖数: 710 | 9 其实可以用01稀疏矩阵里找连续的的1的方法。贴个我的代码。注意因为输入的是char
类型的矩阵，所以这个只能过小集合。简单改一下用int矩阵存起来就能过大集合了。
时间复杂度O(m*n)
class Solution {
public:
void solve(vector> &board) {
int m = board.size();
if(m <= 1) return;
int n = board[0].size();
if(n <= 1) return;
char count = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(board[i][j] == 'O')
board[i][j] = ++count;
set margins;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(board[i][j] != 'X'){
if(i!=0 && board[i-1][j] != 'X')
board[i][j] = board[i-1][j];
else if(j!=0 && board[i][j-1] != 'X')
board[i][j] = board[i][j-1];
if(i==0 || i==m-1 || j==0 || j==n-1)
margins.insert(board[i][j]);
}
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(board[i][j] != 'X')
if(margins.find(board[i][j])!=margins.end())
board[i][j] = 'O';
else
board[i][j] = 'X';
}
}; | l***i
发帖数: 1309 | 10 比较懒，dfs改成了bfs，不过function还是叫dfs
我觉得自己用stack做nonrecursive的dfs也能过，不过没试
【在 p*****2 的大作中提到】
:
: work.
: LZ的不是dfs吧？我倒是在你的code里边看到dfs了。
| p*****2
发帖数: 21240 | 11
应该能过。
【在 l***i 的大作中提到】
: 比较懒，dfs改成了bfs，不过function还是叫dfs
: 我觉得自己用stack做nonrecursive的dfs也能过，不过没试
|
|
