Class Solution
java.lang.Object
g1201_1300.s1210_minimum_moves_to_reach_target_with_rotations.Solution
1210 - Minimum Moves to Reach Target with Rotations.<p>Hard</p>
<p>In an <code>n*n</code> grid, there is a snake that spans 2 cells and starts moving from the top left corner at <code>(0, 0)</code> and <code>(0, 1)</code>. The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at <code>(n-1, n-2)</code> and <code>(n-1, n-1)</code>.</p>
<p>In one move the snake can:</p>
<ul>
<li>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.</li>
<li>Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.</li>
<li>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 <code>(r, c)</code> and <code>(r, c+1)</code> to <code>(r, c)</code> and <code>(r+1, c)</code>.<br />
<img src="https://assets.leetcode.com/uploads/2019/09/24/image-2.png" alt="" /></li>
<li>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 <code>(r, c)</code> and <code>(r+1, c)</code> to <code>(r, c)</code> and <code>(r, c+1)</code>.<br />
<img src="https://assets.leetcode.com/uploads/2019/09/24/image-1.png" alt="" /></li>
</ul>
<p>Return the minimum number of moves to reach the target.</p>
<p>If there is no way to reach the target, return <code>-1</code>.</p>
<p><strong>Example 1:</strong></p>
<p><strong><img src="https://assets.leetcode.com/uploads/2019/09/24/image.png" alt="" /></strong></p>
<p><strong>Input:</strong></p>
<pre><code> 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]]
</code></pre>
<p><strong>Output:</strong> 11</p>
<p><strong>Explanation:</strong> One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].</p>
<p><strong>Example 2:</strong></p>
<p><strong>Input:</strong></p>
<pre><code> 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]]
</code></pre>
<p><strong>Output:</strong> 9</p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>2 <= n <= 100</code></li>
<li><code>0 <= grid[i][j] <= 1</code></li>
<li>It is guaranteed that the snake starts at empty cells.</li>
</ul>
-
Constructor Summary
Constructors -
Method Summary
-
Constructor Details
-
Solution
public Solution()
-
-
Method Details
-
minimumMoves
public int minimumMoves(int[][] grid)
-