二元矩阵的欧拉特性

Question

二进制矩阵表示平面上的形状。1指的是在那个位置的单位方格。0没有任何意义。背景是0。

例如，矩阵[[0,1,0],[0,0,1],[1,1,1]]表示以下形状：

     o----o
     |////|
     |////|
     o----o----o
          |////|
          |////|
o----o----o----o
|////|////|////|
|////|////|////|
o----o----o----o

有几种等价的方法来定义欧拉特性。

一种方法是找出这些正方形的所有顶点和边，并将欧拉特征定义为\chi=V-E+F，其中V是顶点数，E是边数，F是块数。

例如，上面的形状有13顶点、17边和5块。因此，它的欧拉特性是13-17+5=1。

等效定义是形状中连接区域的总数，减去这些区域内出现的孔数。对角连通的区域被认为是连通的，而对角连通的孔则被认为是断开的。

例如，上述形状具有1连接区域和0孔。因此，它的欧拉特性是1-0=1。

请注意，欧拉特性有另一种但不等价的定义，其中对角连通的区域被认为是不连通的，而对角连通的洞则被认为是连通的。使用该定义，上述形状的欧拉特征将是2。

任务

给出一个二元矩阵，找出它的欧拉特性。

对于二进制矩阵，可以使用任意两个一致的值，而不是0和1。

这是密码-高尔夫，所以以字节为单位的最短代码获胜。

测试案例

[[1]] -> 1
[[1,0,1]] -> 2
[[1,0],[0,1]] -> 1
[[0,1,0],[0,0,1],[1,1,1]] -> 1
[[0,1,1,0],[1,0,1,1],[1,1,0,1],[0,1,1,0]] -> -1
[[0,0,1,1,0],[0,1,1,1,1],[1,1,0,1,1],[0,1,1,0,0]] -> 0
[[1,1,1,0,1,1,1],[1,0,1,0,1,0,1],[1,1,1,0,1,1,1]] -> 0
[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]] -> 1

Answer 1

木炭，36字节

ＦＡ«Ｆι«ＦκＵＯ³@#¶#@→→»⸿⸿»≔⁻№ＫＡ@№ＫＡ#θ⎚Ｉθ

在网上试试！链接是详细的代码版本。解释：

ＦＡ«Ｆι«ＦκＵＯ³@#¶#@→→»⸿⸿»

绘制由矩阵表示的形状，但在顶点和面处使用3×3正方形，顶点和面处用@s，边缘使用#s。

≔⁻№ＫＡ@№ＫＡ#θ

从顶点和面的数目中减去最后的边数。

⎚Ｉθ

清除画布并输出结果。

示例:最后一次测试用例[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]的结果如下：

@#@#@#@#@#@
#@#@#@#@#@#
@#@#@#@#@#@
#@#     #@#
@#@ @#@ @#@
#@# #@# #@#
@#@ @#@ @#@
#@#     #@#
@#@#@#@#@#@
#@#@#@#@#@#
@#@#@#@#@#@

这里有53 @s和52 #s，所以它的特点是1。

Answer 2

带图像包的

八度，7字节

bweuler

在网上试试！

一个内置的。

八度，49字节

@(m)sum(conv2(m,[1,2;4,8])(:)==[1,6,7])*[1;-1;-1]

在网上试试！

基于这篇博客文章。欧拉特征是M_1-M_2-M_3，其中M_1，M_2，M_3分别是形式\bigl(\begin{smallmatrix}1&0\\0&0\end{smallmatrix}\bigr)，\bigl(\begin{smallmatrix}1&1\\1&0\end{smallmatrix}\bigr)，\bigl(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\bigr)的2\times2子矩阵的个数。

感谢@Cris Luengo指出这是格雷的算法。

Answer 3

Python3,606字节：

E=enumerate
def V(m,x,y):
 if x>=0 and y>=0:
  try:return m[x][y]
  except:return 0
def f(m):
 s,R=[],[0,0]
 while(O:=[(x,y)for x,b in E(m)for y,_ in E(b)if m[x][y]and(x,y)not in s]):
  q=[O[0]]
  while q:
   x,y=q.pop(0)
   M,D=[(0,1),(0,-1),(1,0),(-1,0)],[(-1,-1),(-1,1),(1,-1),(1,1)]
   if(x,y)in s:continue
   s+=[(x,y)]
   for u,v in M:
    R[1]+=(p:=(x+u,y+v))not in s
    if V(m,*p)and p not in s:q+=[p]
   for u,v in D:
    R[0]+=(p:=(x+u,y+v))not in s and all((x+u+j,y+v+k)not in s for j,k in[(0,[-1,1][v<1]),([-1,1][u<1],0)])
    if V(m,*p)and p not in s:q+=[p] 
 return R[0]-R[1]+sum(map(sum,m))

在网上试试！