公路高尔夫穿越山间

Question

你在电网上有很多城市，你想把它们连接起来。道路可以放置在任何不包含城市的瓷砖上，并连接到所有道路或与其相邻的城市，垂直、水平或对角线。

例如，道路可以通过城市连接起来。

C
 \
  C-C

完全连在一起。

然而，有些山挡在你的路上。道路不能穿过山脉，必须绕山而行。在我的示例/测试案例中，它们将被标记为M。

使用

  M
C M C
  M

有点像

  ^
 /M\
C M C
  M

一定要做好。

例如，道路可以通过对角线通过山口。

C M
 \M
MM\
   C

是有效的。

你的挑战

考虑到城市和山区的布局，输出连接所有城市和山区所需的最少数量的道路。

规则

输入可以采取任何你喜欢，如艺术，矩阵，城市和山区的位置，等等。

您可能会假设不会输入任何邻近的城市(如CC)。

测试案例

注意:这些文件被格式化为ASCII-art。

C C 
=> 1

C C
  
  C
=> 1 (in the centre)

C M C
=> 3

MMC
  M
C M
=> 1

MMMMMMMMM
MCMCM   M
M M M M M
M M   M M
M MMMMM M
M       M
MMMMMMMMM
=> 15

C   C
  C

  C
C   C
=> 5

MMM
CMC
MMM
=> 5

     C
MMMMMMMMMM
C        C
=> 11

Answer 1

Python 3 + numpy，325个字节

我的05AB1E解决方案的一个(稍快)端口。计算复杂度保持不变，但尤其是矩阵运算速度更快。

from itertools import*
from numpy import*
def f(G):
 E=enumerate;k=[' '];p,c,*s=[k*len(G[0])],[]
 for y,r in E([k+r+k for r in p+G+p]):
  for x,v in E(r):[s,p,p,c][ord(v)%4]+=[y,x],
 for i in count():
  for N in combinations(s,i):
   v=array(c+[*N]);A=sum((v-v[:,None])**2,axis=2)<3
   for _ in v:A=A@A
   if A.min():return i

在网上试试！

非高尔夫项目：

import itertools, sys
import numpy as np

grid = [list(line) for line in sys.stdin.read().splitlines()]
print(grid)
width = len(grid[0])

# pad with spaces on all sides
padding = [[' '] * width]
grid = [[' ', *row, ' '] for row in padding + grid + padding]

# get the coordinates of cities and empty spaces
cities = [[y, x] for y, row in enumerate(grid) for x, v in enumerate(row) if 'C' == v]
spaces = [[y, x] for y, row in enumerate(grid) for x, v in enumerate(row) if ' ' == v]

for i in range(len(spaces)):
  # Iterate over all combinations of i new cities
  for new_cities in itertools.combinations(spaces, i):
    vertices = np.array([*cities, *new_cities])
    adjacency = (np.sum((vertices - vertices[:, None])**2, axis=-1)<3)
    if (np.linalg.matrix_power(adjacency, adjacency.shape[0]) > 0).all():
      print(i)
      exit()

在网上试试！