最小化5x5二进制板上最长的王链

解答动态

• 

  1 2 3 4-+----A
• 

  1 0 0 0B
• 

  0 1 1C
• 

  1 0 0 1D
• 

  0 1 0 1当0上最长的王链长度为7（D3-C3-C2-。。。-A4），最大长度相同（D2-。。。-D4）.
  现在，你能找到一个5x5的网格，里面充满了0和1，这样在每对0和每对1都通过某个王链连接的约束下，最长的王链是最短的吗？
  ：如果我们删除约束呢？
  
• 

  作为第一次尝试，最长的8条王链：
  0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 1 1 0
  1s将网格拆分为四个零象限，因此任何零路径的长度最多为7（象限的2+中心）。路径1从任何一边开始，在中间循环，然后以8的长度退出。
  作为奖励，
  0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0最大长度5
  非常确定它不能降低-我不认为有一种方法可以用少于5个连接的1来封装任何一组四个国王连接的零。
  
• End