在一个 10×10 的网格中,农民 John 和两头牛(始终在一起)在移动。网格中有些格子是障碍物,John 和牛都不能进入障碍物格子。
移动规则:
每分钟,它们可以向前移动一步,或者转弯。
- 如果前方(当前朝向)是空地(即不是障碍物且不越界),则向前移动一步。
- 否则,原地顺时针旋转 90 度(不移动)。
John 和牛的移动是同时进行的。如果某一分钟结束后,他们在同一个格子相遇,则追捕结束。
注意:如果他们在移动过程中“穿过”对方(即交换位置),但没有在某一分钟结束时位于同一格,则不算相遇。
开始时,John 和牛都面向北方。
给定地图,请计算 John 抓住牛所需的最少分钟数。如果 John 永远无法抓住牛,则输出 0。