1210. Minimum Moves to Reach Target with Rotations¶
题目信息¶
- 题号:
1210
- 难度:
Hard
- 主题:
网格、广度优先搜索、状态转换、旋转
- 原题:
- 重点:
蛇占据两个相邻格,状态包含尾部坐标和方向;移动或旋转涉及的所有格子都必须为空
题目重述¶
在 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),因此无法执行第一步。