|
1 | 1 | packagecom.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 | publicclass_980 { |
40 | 4 | publicstaticclassSolution1 { |
41 | 5 |
|
|