来考验坛友们的数学水平了（答案已公布在52楼，71楼补充了图）

ryanghj

isengrin 发表于 2024-7-20 22:50
那你从11行如何到12行

11行往后都是i列，因为i列的坏人已经出现在a行了所以往后都没有坏人了

骷髅兵

今井莉莎 发表于 2024-7-20 22:58
公布答案吧，答案就是3次，其实6楼的哥们已经画图做出来这题的一半了，采取如下策略，从第1行的最右边开始 ...

我感觉3次好像不够吧，万一是几条交叉线段呢？比如这样？

ganxin225

想到了对角分布，可惜没有想到能贴着对角线走，碰到了就说明对角分布被打破了可以绕过去。

BRRM

骷髅兵 发表于 2024-7-21 01:04
我感觉3次好像不够吧，万一是几条交叉线段呢？比如这样？

红色是第一次，当进入第二行的时候立刻撞墙
蓝色是第二次，按照方法2从左到右遍历第三行，不用撞到第三行的墙就能推断出那里有一度墙，遍历到第四行中间的时候撞墙了。
紫色是第三次，根据第一次和第二次的线索，可以知道哪里是安全的，即第四行除了那堵墙以外都是安全的， 倒数第一列除了第一行都是安全的，倒数第二列除了第二行都是安全的。

Hydro

骷髅兵 发表于 2024-7-21 01:04
我感觉3次好像不够吧，万一是几条交叉线段呢？比如这样？

dm只有两种战术，是完整对角线/不是完整对角线
是完整对角线则贴边可以走到底，不是的话则可能撞死一次（也可能不会，假如dm乱下无意义的子），然后作为pl在那行投奔已经知道排除问题的列
最简单的模型是3列2子

Hydro

你们横走干什么...只有第一行需要全行扫描吧

zorya

骷髅兵 发表于 2024-7-21 01:04
我感觉3次好像不够吧，万一是几条交叉线段呢？比如这样？

可以的。
3次尝试分别为红，蓝，绿

Tienx

Hydro 发表于 2024-7-21 01:19
你们横走干什么...只有第一行需要全行扫描吧

不扫第二行怎么推测第二行坏人在哪，你LS那个就是正确步骤了

Hydro

Tienx 发表于 2024-7-21 01:32
不扫第二行怎么推测第二行坏人在哪，你LS那个就是正确步骤了

你的第一行是起始行还是第一个可能有雷的行，只有第一个有雷的行需要遍历

Hydro

Tienx 发表于 2024-7-21 01:32
不扫第二行怎么推测第二行坏人在哪，你LS那个就是正确步骤了

71楼官方，或76楼我的，我画图的时候还没看到官方图，但是是一个东西
我大概理解后续几行还在遍历是想确认安全范围，但没必要，直接对角线走更优雅更理解问题本质

骷髅兵

明白了，第一步横走确定线段或点的开始位置，第二步确定缺口位置和安全范围，第三步就能绕过去了，数学已经忘光光了，不看图已经想像不出步骤了

幻想风靡_

自己走阶梯有点天才了，确实没想到

—— 来自 S1Fun

ifrush

感觉这个题如果作为codeforces上面constructive algorithms的题目的话，能做出来的人估计还是不少的。