发火鸡了吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

发火鸡了吗？

发火鸡了吗？# Joke - 肚皮舞运动

h*i2012-11-21 08:11

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';
}
}
}
}

}

j*c2012-11-21 08:11

2 楼

m*d2012-11-21 08:11

3 楼

还是我又来晚了？

p*22012-11-21 08:11

4 楼

系统不稳定。我这个dfs也是要run很多次才能过一次。不过我两个都实现了。
http://blog.sina.com.cn/s/blog_b9285de20101j1dt.html

v*l2012-11-21 08:11

5 楼

木有。

t*Q2012-11-21 08:11

6 楼

版主，今年养鸡了吗？

【在 m*****d 的大作中提到】

: 还是我又来晚了？

p*e2012-11-21 08:11

7 楼

我的也不行，怎么检查代码都出错，小数据没问题

S*t2012-11-21 08:11

8 楼

没。

f*t2012-11-21 08:11

9 楼

什么错？

【在 p****e 的大作中提到】

: 我的也不行，怎么检查代码都出错，小数据没问题

k*n2012-11-21 08:11

10 楼

大家给包子机一点时间

【在 j****c 的大作中提到】

: rt

l*i2012-11-21 08:11

11 楼

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; jint 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; iint 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; ifor (int j=0; jif (board[i][j] == marker) board[i][j] = 'O';
else if (board[i][j] == 'O') board[i][j] = 'X';
}
};

f*p2012-11-21 08:11

12 楼

没

【在 j****c 的大作中提到】

: rt

p*22012-11-21 08:11

13 楼

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;

j*32012-11-21 08:11

14 楼

re

【在 j****c 的大作中提到】

: rt

h*i2012-11-21 08:11

15 楼

你的这个从四边往中间走的思路好，什么都不用记了。

【在 p*****2 的大作中提到】

:
: work.
: LZ的不是dfs吧？我倒是在你的code里边看到dfs了。

j*c2012-11-21 08:11

16 楼

包子机是啥东东？我每次都是手动发包子，累死

【在 k*****n 的大作中提到】

: 大家给包子机一点时间

h*i2012-11-21 08:11

17 楼

贴个旁门左道。 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 的大作中提到】

: 你的这个从四边往中间走的思路好，什么都不用记了。

L*k2012-11-21 08:11

18 楼

有两种。
一种是抢包子的
一种是发包子的

【在 j****c 的大作中提到】

: 包子机是啥东东？我每次都是手动发包子，累死

w*a2012-11-21 08:11

19 楼

其实可以用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';

}
};