一道计算物体周长题

做OA的时候遇到了一道题

给定一个二维数组， 每个物体可以从八个方向连接，计算所有形成的物体的周长和。

case1

input:
0 0 0 0 0
1 0 0 0 0
1 1 0 0 0
0 0 0 1 1
0 0 0 1 1

output:
16

case2:
1 1 1 1 0
1 0 0 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 1 0

output:
20

https://leetcode.com/problems/island-perimeter/

337845818 发表于 2019-11-19 03:26
https://leetcode.com/problems/island-perimeter/

跟这道题不太一样，每个格子可以跟八个方向的格子连接形成物体比如下面的这个周长是12：
0 1 0
1 0 1
0 1 0

而且如果物体内部有空心的话呗包围的小物体的周长不算

xt2017 发表于 2019-11-19 07:42
跟这道题不太一样，每个格子可以跟八个方向的格子连接形成物体比如下面的这个周长是12：
0 1 0
1 0 1

把连上边界的0 dfs成2
然后把0和1都当成1
不太确定你的题意是这样吗？

anhpp 发表于 2019-11-19 10:33
把连上边界的0 dfs成2
然后把0和1都当成1
不太确定你的题意是这样吗？

应该是的

dfs 物体的边界 遍历时候注意每个点有 上 下 左 右 四个 边界，所以每个点有四个状态 用4个 bit. 遍历的时候要注意对角的特殊case
0 1
1 0

case 1  中间的1 周长可以连起来
000
010
100

case2 第二行的1 周长不一定能连
011
010
100
100

最后把同一物体的周长类似染色 分成n种， 每种分开记录min x ，max x，max y，min y ， max 最大 或min 最小的
就是周长

lyronly 发表于 2019/11/23 05:40:38
dfs 物体的边界 遍历时候注意每个点有 上 下 左 右 四个 边界，所以每个点有四个状态 用4个 bit. 遍历的时候...

最后把同一物体的周长类似染色 分成n种， 每种分开记录min x ，max x，max y，min y ， max 最大 或min 最小的就是外围周长

如果一个物体有多个周长 就dfs把不是外围周长的填了 ，排除掉物体中心被包围的其他物体