puzzle(1131)指路罗马

目录

指路罗马

规则

4*4

6*6

8*8

贪心算法

10*10


指路罗马

规则

给定了终点(可能不唯一)和部分箭头,填充所有的空格,每个空格都是四个方向的箭头之一,使得两条限制条件成立。

限制条件一:从任意一个箭头出发都能到达终点。

限制条件二:每个框出来的区域里面,1-4个箭头的方向各不相同。

4*4

6*6

8*8

这一步,利用贪心算法,即可推出一定存在一个解满足“第一行第八列是往下的箭头”。

如果这个puzzle保证有唯一解,那推出来的就是“第一行第八列一定是往下的箭头”。

贪心算法

AB是两个相邻的格子,如果已知不存在A间接指向B的解,且把B直接指向A不会因为限制条件二而影响其他格子那么就一定存在一个解满足“B直接指向A”。

其中,A间接指向B,指的是A到终点的路径上会经过B。

其中,B选择某个方向,“不会因为限制条件二而影响其他格子”的常见(但并非唯一)情形就是,B是所在框框内的最后一个格子。

10*10