给你一个 m x n
的二进制矩形 grid
和一个整数 health
表示你的健康值。
你开始于矩形的左上角 (0, 0)
,你的目标是矩形的右下角 (m - 1, n - 1)
。
你可以在矩形中往上下左右相邻格子移动,但前提是你的健康值始终是 正数 。
对于格子 (i, j)
,如果 grid[i][j] = 1
,那么这个格子视为 不安全 的,会使你的健康值减少 1 。
如果你可以到达最终的格子,请你返回 true
,否则返回 false
。
注意 ,当你在最终格子的时候,你的健康值也必须为 正数 。
示例 1:
输入:grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1
输出:true
解释:
沿着下图中灰色格子走,可以安全到达最终的格子。
示例 2:
输入:grid = [[0,1,1,0,0,0],[1,0,1,0,0,0],[0,1,1,1,0,1],[0,0,1,0,1,0]], health = 3
输出:false
解释:
健康值最少为 4 才能安全到达最后的格子。
输入:grid = [[1,1,1],[1,0,1],[1,1,1]], health = 5
输出:true
解释:
沿着下图中灰色格子走,可以安全到达最终的格子。
任何不经过格子 (1, 1)
的路径都是不安全的,因为你的健康值到达最终格子时,都会小于等于 0 。
----------
因为可以上下左右走,不能只是向右或者向下,所以直接dp的话,我不会,就只能BFS处理,这里更新vis数组的时候还错了。。。必须new_health>vis[nx][ny]的时候,才能把数组放入que,不能>=的时候就放进去,不然就超时了。。。不经意的一个符号,就错很多啊。。