1210. Minimum Moves to Reach Target with Rotations

题目信息

题号:

1210

难度:

Hard

主题:

网格、广度优先搜索、状态转换、旋转

原题:

LeetCode 1210

重点:

蛇占据两个相邻格,状态包含尾部坐标和方向;移动或旋转涉及的所有格子都必须为空

题目重述

在 n x n 二进制网格中,0 表示空格,1 表示障碍。蛇初始水平占据 (0,0) 和 (0,1),目标是水平占据 (n-1,n-2) 和 (n-1,n-1)。

蛇可以向右或向下平移;处于水平状态时,在下方两个格子都为空的条件下可顺时针旋转为竖直状态;处于竖直状态时,在右侧两个格子都为空的条件下可逆时针旋转为水平状态。请返回到达目标所需的最少操作数,不可达时返回 -1。

2 <= n <= 100,grid 为 n x n 的二进制矩阵,起始与目标占用格保证为空。

自建示例

空网格中只需连续向下移动:

输入:grid = [[0,0,0],[0,0,0],[0,0,0]]
输出:2
解释:蛇保持水平状态向下移动两次,直接到达最后一行的目标位置。

起点周围被障碍封死:

输入:grid = [[0,0,1],[1,0,1],[1,0,0]]
输出:-1
解释:蛇不能向右,向下与顺时针旋转也都需要使用障碍格 (1,0),因此无法执行第一步。