【leetcode】1210. Minimum Moves to Reach Target with Rotations
2024-08-31 15:52:17
题目如下:
In an
n*n
grid, there is a snake that spans 2 cells and starts moving from the top left corner at(0, 0)
and(0, 1)
. The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at(n-1, n-2)
and(n-1, n-1)
.In one move the snake can:
- Move one cell to the right if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
- Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
- Rotate clockwise if it's in a horizontal position and the two cells under it are both empty. In that case the snake moves from
(r, c)
and(r, c+1)
to(r, c)
and(r+1, c)
.- Rotate counterclockwise if it's in a vertical position and the two cells to its right are both empty. In that case the snake moves from
(r, c)
and(r+1, c)
to(r, c)
and(r, c+1)
.Return the minimum number of moves to reach the target.
If there is no way to reach the target, return
-1
.Example 1:
Input: grid = [[0,0,0,0,0,1],
[1,1,0,0,1,0],
[0,0,0,0,1,1],
[0,0,1,0,1,0],
[0,1,1,0,0,0],
[0,1,1,0,0,0]]
Output: 11
Explanation:
One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].Example 2:
Input: grid = [[0,0,1,1,1,1],
[0,0,0,0,1,1],
[1,1,0,0,0,1],
[1,1,1,0,0,1],
[1,1,1,0,0,1],
[1,1,1,0,0,0]]
Output: 9Constraints:
2 <= n <= 100
0 <= grid[i][j] <= 1
- It is guaranteed that the snake starts at empty cells.
解题思路:典型的BFS题目。特别要注意的是蛇在水平/垂直方向是可以平移的。比如当前所在的左边是(0,0)(0,1),可以平移到(1,0),(1,1)。
代码如下:
class Solution(object):
def minimumMoves(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
res = float('inf')
queue = [(0,0,0,1,0)]
dic = {}
dic[(0,0,0,1)] = 0
while len(queue) > 0:
tx,ty,hx,hy,count = queue.pop(0)
#print tx,ty,hx,hy,count
if hx == len(grid) - 1 == hy and tx == len(grid)-1 and ty == len(grid) - 2:
res = min(res,count)
continue
if tx == hx and ty < hy: #head to right
if hy + 1 < len(grid) and grid[hx][hy+1] == 0:
key = (tx,ty+1,hx,hy+1)
if key not in dic or dic[key] > count + 1:
queue.append((tx,ty+1,hx,hy+1,count+1))
dic[key] = count + 1
if hx + 1 < len(grid) and grid[tx+1][ty] == 0 and grid[hx+1][hy] == 0:
key = (tx, ty, hx+1, ty)
if key not in dic or dic[key] > count + 1:
queue.append((tx, ty, hx+1, ty, count + 1))
dic[key] = count + 1
key = (tx+1,ty,hx+1,hy)
if key not in dic or dic[key] > count + 1:
queue.append((tx+1,ty,hx+1,hy, count + 1))
dic[key] = count + 1
elif tx < hx and ty == hy: #head to down
if hx + 1 < len(grid) and grid[hx+1][hy] == 0:
key = (tx+1,ty,hx+1,hy)
if key not in dic or dic[key] > count + 1:
queue.append((tx+1,ty,hx+1,hy,count+1))
dic[key] = count + 1
if hy + 1 < len(grid) and grid[hx][hy+1] == 0 and grid[tx][ty+1] == 0:
key = tx,ty,tx,ty+1
if key not in dic or dic[key] > count + 1:
queue.append((tx,ty,tx,ty+1,count+1))
dic[key] = count + 1
key = tx, ty+1, tx, ty + 1
if key not in dic or dic[key] > count + 1:
queue.append((tx,ty+1,hx,hy+1,count+1))
dic[key] = count + 1
return res if res != float('inf') else -1
最新文章
- spring加载bean实例化顺序
- 视频演示eworkflow集成定制aspx页面的过程
- temp_web
- HTML5新特性之Web Worker
- TFS 2013 配置的时候,提示TF255466错误
- MySQL学习笔记(二)
- python知识点(07-08)
- SQL2005以上行变行简单实现
- CentOS 6.4 64位 搭建MySQL-Cluster 7.3.8 集群
- 使用kolin开发你的android应用
- JDBC笔记总结[申明:来源于网络]
- Cocos Creator 使用protobufjs
- HDU 2033 人见人爱A+B
- STLの应用
- day24,25组合 封装 多态
- Java 经典面试题 —— 性能
- 用 CentOS 7 打造合适的科研环境
- JasperReport学习札记6-JRXML的标签
- Mac下更新SVN
- docker 下载加速
热门文章
- Python学习之UDP版socket&;SocketServer
- python学习之数据类型(dic)
- LeetCode.1030-曼哈顿距离排序矩阵单元格(Matrix Cells in Distance Order)
- LeetCode.977-排序数组的平方(Squares of a Sorted Array)
- 【神经网络与深度学习】【CUDA开发】【VS开发】Microsoft官方移植了Caffe配置过程说明
- Python密码登录程序的思考--学与习
- C#各种委托介绍
- python logger理解
- [转帖]Linux网络管理员不得不了解的系统目录/proc/sys/net/(网络配置)
- java遇到的笔试题