mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-09-05 15:31:43 +08:00
135 lines
5.7 KiB
HTML
135 lines
5.7 KiB
HTML
<p>Given an <code>m x n</code> binary grid <code>grid</code> where:</p>
|
|
|
|
<ul>
|
|
<li><code>grid[i][j] == 0</code> represents an empty cell, and</li>
|
|
<li><code>grid[i][j] == 1</code> represents a mirror.</li>
|
|
</ul>
|
|
|
|
<p>A robot starts at the top-left corner of the grid <code>(0, 0)</code> and wants to reach the bottom-right corner <code>(m - 1, n - 1)</code>. It can move only <strong>right</strong> or <strong>down</strong>. If the robot attempts to move into a mirror cell, it is <strong>reflected</strong> before entering that cell:</p>
|
|
|
|
<ul>
|
|
<li>If it tries to move <strong>right</strong> into a mirror, it is turned <strong>down</strong> and moved into the cell directly below the mirror.</li>
|
|
<li>If it tries to move <strong>down</strong> into a mirror, it is turned <strong>right</strong> and moved into the cell directly to the right of the mirror.</li>
|
|
</ul>
|
|
|
|
<p>If this reflection would cause the robot to move outside the <code>grid</code> boundaries, the path is considered invalid and should not be counted.</p>
|
|
|
|
<p>Return the number of unique valid paths from <code>(0, 0)</code> to <code>(m - 1, n - 1)</code>.</p>
|
|
|
|
<p>Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>
|
|
|
|
<p><strong>Note</strong>: If a reflection moves the robot into a mirror cell, the robot is immediately reflected again based on the direction it used to enter that mirror: if it entered while moving right, it will be turned down; if it entered while moving down, it will be turned right. This process will continue until either the last cell is reached, the robot moves out of bounds or the robot moves to a non-mirror cell.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">grid = [[0,1,0],[0,0,1],[1,0,0]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">5</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<table style="border: 1px solid black;">
|
|
<thead>
|
|
<tr>
|
|
<th align="center" style="border: 1px solid black;">Number</th>
|
|
<th align="left" style="border: 1px solid black;">Full Path</th>
|
|
</tr>
|
|
</thead>
|
|
<tbody>
|
|
<tr>
|
|
<td align="center" style="border: 1px solid black;">1</td>
|
|
<td align="left" style="border: 1px solid black;">(0, 0) → (0, 1) [M] → (1, 1) → (1, 2) [M] → (2, 2)</td>
|
|
</tr>
|
|
<tr>
|
|
<td align="center" style="border: 1px solid black;">2</td>
|
|
<td align="left" style="border: 1px solid black;">(0, 0) → (0, 1) [M] → (1, 1) → (2, 1) → (2, 2)</td>
|
|
</tr>
|
|
<tr>
|
|
<td align="center" style="border: 1px solid black;">3</td>
|
|
<td align="left" style="border: 1px solid black;">(0, 0) → (1, 0) → (1, 1) → (1, 2) [M] → (2, 2)</td>
|
|
</tr>
|
|
<tr>
|
|
<td align="center" style="border: 1px solid black;">4</td>
|
|
<td align="left" style="border: 1px solid black;">(0, 0) → (1, 0) → (1, 1) → (2, 1) → (2, 2)</td>
|
|
</tr>
|
|
<tr>
|
|
<td align="center" style="border: 1px solid black;">5</td>
|
|
<td align="left" style="border: 1px solid black;">(0, 0) → (1, 0) → (2, 0) [M] → (2, 1) → (2, 2)</td>
|
|
</tr>
|
|
</tbody>
|
|
</table>
|
|
|
|
<ul data-end="606" data-start="521">
|
|
<li data-end="606" data-start="521">
|
|
<p data-end="606" data-start="523"><code>[M]</code> indicates the robot attempted to enter a mirror cell and instead reflected.</p>
|
|
</li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">grid = [[0,0],[0,0]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">2</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<table style="border: 1px solid black;">
|
|
<thead>
|
|
<tr>
|
|
<th align="center" style="border: 1px solid black;">Number</th>
|
|
<th align="left" style="border: 1px solid black;">Full Path</th>
|
|
</tr>
|
|
</thead>
|
|
<tbody>
|
|
<tr>
|
|
<td align="center" style="border: 1px solid black;">1</td>
|
|
<td align="left" style="border: 1px solid black;">(0, 0) → (0, 1) → (1, 1)</td>
|
|
</tr>
|
|
<tr>
|
|
<td align="center" style="border: 1px solid black;">2</td>
|
|
<td align="left" style="border: 1px solid black;">(0, 0) → (1, 0) → (1, 1)</td>
|
|
</tr>
|
|
</tbody>
|
|
</table>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 3:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">grid = </span>[[0,1,1],[1,1,0]]</p>
|
|
|
|
<p><strong>Output:</strong> 1</p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<table style="border: 1px solid black;">
|
|
<thead>
|
|
<tr>
|
|
<th align="center" style="border: 1px solid black;">Number</th>
|
|
<th align="left" style="border: 1px solid black;">Full Path</th>
|
|
</tr>
|
|
</thead>
|
|
<tbody>
|
|
<tr>
|
|
<td align="center" style="border: 1px solid black;">1</td>
|
|
<td align="left" style="border: 1px solid black;">(0, 0) → (0, 1) [M] → (1, 1) [M] → (1, 2)</td>
|
|
</tr>
|
|
</tbody>
|
|
</table>
|
|
<code>(0, 0) → (1, 0) [M] → (1, 1) [M] → (2, 1)</code> goes out of bounds, so it is invalid.</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li data-end="41" data-start="21"><code data-end="39" data-start="21">m == grid.length</code></li>
|
|
<li data-end="67" data-start="44"><code data-end="65" data-start="44">n == grid[i].length</code></li>
|
|
<li data-end="91" data-start="70"><code data-end="89" data-start="70">2 <= m, n <= 500</code></li>
|
|
<li data-end="129" data-start="94"><code data-end="106" data-start="94">grid[i][j]</code> is either <code data-end="120" data-is-only-node="" data-start="117">0</code> or <code data-end="127" data-start="124">1</code>.</li>
|
|
<li data-end="169" data-start="132"><code data-end="167" data-start="132">grid[0][0] == grid[m - 1][n - 1] == 0</code></li>
|
|
</ul>
|