如何找到矩阵中最长的蛇

Question

想象我们有一条蛇包含在矩阵[a][b]中：它高a，宽b。如果矩阵中的单元格位于另一个单元格的直接、上方、下方、左侧或右侧，则可以将其视为邻居。对角细胞不是邻居。矩阵内的蛇必须是连续的，其长度由其占据的单元数计算。蛇的宽度为 1 个单元格，它可以占据矩阵内的任何单元格，但不能离开矩阵。蛇可以在矩阵内旋转 90 度，但不能接触自身。这意味着蛇内的每个细胞必须恰好有两个邻居，而头部和尾部必须只有 1 个邻居。

在示例中，蛇位于蓝色的 3 x 9 矩阵中。

无效的蛇看起来像这样：红色圆圈突出显示蛇接触自身的位置。

一条有效的蛇看起来像这样：

这条蛇有 19 个细胞长。

蛇不需要从角落开始。在某些情况下，它会导致蛇更长：

这条蛇有 20 个细胞长。

问题是，在任何给定的矩阵[a][b]中找到的最长蛇的长度是多少？有没有图遍历算法来求长度？我们可以不用遍历图形而用公式求出长度吗？

我们尝试暴力解决这个问题，但似乎解决方案效率低下。我们感兴趣的是是否有数学公式或已知算法来解决这个问题。任何有关此主题的论文或文章的链接都会有帮助！

Answer 1

我还没有在互联网上搜索过（快速扫描后示例文章）。

对于给定的示例，以下 MiniZinc 约束规划模型也达到长度

20

。

int: rows = 3;
int: cols = 9;
set of int: Rows = 1..rows;
set of int: Cols = 1..cols;

%  a cell with true value belongs to a snake
array[Rows, Cols] of var bool: cells;

function var bool: has_neighbour(int: row, int: col, int: dRow, int: dCol) =
  ((row + dRow) in Rows) /\ ((col + dCol) in Cols) /\ cells[row + dRow, col + dCol];

function var 1..4: no_of_neighbours(Rows: row, Cols: col) =
  (has_neighbour(row, col, -1, 0) +
   has_neighbour(row, col, +1, 0) +
   has_neighbour(row, col, 0, -1) +
   has_neighbour(row, col, 0, +1));
   
%  a snake cell can have one or two neighbours 
%  (this disallows snakes with length 1)
constraint forall(row in Rows, col in Cols) (
  (not cells[row, col]) \/
  (2 >= no_of_neighbours(row, col))
);

%  there must be exactly one head and one tail
constraint 2 == sum(row in Rows, col in Cols) (
  cells[row, col] /\
  (1 == no_of_neighbours(row, col))
);

solve maximize(sum(cells));

function string: ite(bool: cond, string: sYes, string: sNo) =
  if cond then sYes else sNo endif;
  
output ["length \(sum(cells))"] ++
       [ ite(col == 1, "\n", "") ++ 
         ite(fix(cells[row, col]), "X ", "  ") 
         | row in Rows, col in Cols ];
         

输出：

length 20
X X X   X X X X X 
X     X X       X 
X X X X   X X X X