来问一下leetcode Surrounded Regions - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

来问一下leetcode Surrounded Regions

来问一下leetcode Surrounded Regions# JobHunting - 待字闺中

c*p2013-07-23 07:07

1 楼

这个题，我是这样做的：
1. 从4周(最上一行，和最下一行，然后第一列除去首尾，最后一列除去首尾)找到 O,
把坐标x,y 放到2个queue里。找到的时候，把O标记成了Y.
2. 当queue不为空时
把queue里的坐标poll出来，看这个坐标上下左右，如果是O, add到queue最后。
3. 把矩阵中的O变成X, 把Y变成O.
过的了小oj，过不了大oj
我参考的是这个blog，然后把人家c++代码放进去跑了，就过的了大oj。。。
http://fisherlei.blogspot.com/2013/03/leetcode-surrounded-regio
我哪里耗时耗空间了？？

g*G2013-07-23 07:07

2 楼

2. 当queue不为空时
把queue里的坐标poll出来，看这个坐标上下左右，如果是O, add到queue最后
你有没有标记访问过的点？

c*p2013-07-23 07:07

3 楼

没，我是参照那个blog的方法写的。他一开始有标记点，但发现超时了。后来他不标记
，就不超时了。
这里我也觉得他的方法不妥当。
所以我的方法里，一开始就把o换成y了。

【在 g**G 的大作中提到】

: 2. 当queue不为空时
: 把queue里的坐标poll出来，看这个坐标上下左右，如果是O, add到queue最后
: 你有没有标记访问过的点？

z*e2013-07-23 07:07

4 楼

你不是做完一遍了么？

s*t2013-07-23 07:07

5 楼

没问题啊，刚试了下，就按你说的写的，能通过

,

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

: 这个题，我是这样做的：
: 1. 从4周(最上一行，和最下一行，然后第一列除去首尾，最后一列除去首尾)找到 O,
: 把坐标x,y 放到2个queue里。找到的时候，把O标记成了Y.
: 2. 当queue不为空时
: 把queue里的坐标poll出来，看这个坐标上下左右，如果是O, add到queue最后。
: 3. 把矩阵中的O变成X, 把Y变成O.
: 过的了小oj，过不了大oj
: 我参考的是这个blog，然后把人家c++代码放进去跑了，就过的了大oj。。。
: http://fisherlei.blogspot.com/2013/03/leetcode-surrounded-regio
: 我哪里耗时耗空间了？？