|
1 | 1 | package com.fishercoder.solutions;
|
2 | 2 |
|
3 |
| -/** |
4 |
| - * 980. Unique Paths III |
5 |
| - * |
6 |
| - * On a 2-dimensional grid, there are 4 types of squares: |
7 |
| - * 1 represents the starting square. There is exactly one starting square. |
8 |
| - * 2 represents the ending square. There is exactly one ending square. |
9 |
| - * 0 represents empty squares we can walk over. |
10 |
| - * -1 represents obstacles that we cannot walk over. |
11 |
| - * Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once. |
12 |
| - * |
13 |
| - * Example 1: |
14 |
| - * Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]] |
15 |
| - * Output: 2 |
16 |
| - * Explanation: We have the following two paths: |
17 |
| - * 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2) |
18 |
| - * 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2) |
19 |
| - * |
20 |
| - * Example 2: |
21 |
| - * Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]] |
22 |
| - * Output: 4 |
23 |
| - * Explanation: We have the following four paths: |
24 |
| - * 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3) |
25 |
| - * 2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3) |
26 |
| - * 3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3) |
27 |
| - * 4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3) |
28 |
| - * |
29 |
| - * Example 3: |
30 |
| - * Input: [[0,1],[2,0]] |
31 |
| - * Output: 0 |
32 |
| - * Explanation: |
33 |
| - * There is no path that walks over every empty square exactly once. |
34 |
| - * Note that the starting and ending square can be anywhere in the grid. |
35 |
| - * |
36 |
| - * Note: |
37 |
| - * 1 <= grid.length * grid[0].length <= 20 |
38 |
| - * */ |
39 | 3 | public class _980 {
|
40 | 4 | public static class Solution1 {
|
41 | 5 |
|
|
0 commit comments