Google店面

一周前的谷歌店面
45分钟，白人小哥，面试官介绍完自己，简单问了问我的情况，之后直接做题。
题目是给一个图像，有黑白两种点，写一个方法把图中所有被黑点围住的白点涂黑。
例：0代表白点，1代表黑点
0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 0
0 0 0 0 1 0 0 1

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

0 0 0 1 1 1 0 0
0 0 0 0 1 1 1 0 0

public void fillup(int[][] image){}

先沿壁做dfs/bfs，剩下没被访问的白点全部涂黑，这样是否可行？

frankjing 发表于 2019/10/31 08:30:52
请问一下楼主这道题目是什么思路呢？

从（0，0）开始，每个值为0的都dfs/bfs看看四面能不能有一面到达边界，如果能，什么都不做，如果四面都有1挡着，就把所经过的点都改成1

请问一下楼主这道题目是什么思路呢？

frankjing 发表于 2019/10/31 08:30:52
请问一下楼主这道题目是什么思路呢？

比较像lc130

shuishuixiaoyua 发表于 2019/10/31 08:40:34
比较像lc130

基本上就是lc130

lucius2411 发表于 2019-10-31 13:14
从（0，0）开始，每个值为0的都dfs/bfs看看四面能不能有一面到达边界，如果能，什么都不做，如果四面都有1 ...

这个复杂度是多少呢。。。感觉有点高啊。。。你的意思是往上就一直往上直到撞墙是吗？那复杂度是m*n*(m+n)对吗

路飞之父 发表于 2019-11-3 15:42
这个复杂度是多少呢。。。感觉有点高啊。。。你的意思是往上就一直往上直到撞墙是吗？那复杂度是m*n*(m+n ...

哦哦我搞错了。。。。。

用Union-find不知道行不行，所有是0且能union到（0， 0）点 的都union到（0， 0）点，剩下的0都涂黑好像就行了。。。

williamshi 发表于 2019-11-5 14:31
用Union-find不知道行不行，所有是0且能union到（0， 0）点 的都union到（0， 0）点，剩下的0都涂黑好像就 ...

那如何区分圈里面的0和圈外面的0呢？