980. Unique Paths III Hard

1/**
2 * [980] Unique Paths III
3 *
4 * You are given an m x n integer array grid where grid[i][j] could be:
5 * 
6 * 	1 representing the starting square. There is exactly one starting square.
7 * 	2 representing the ending square. There is exactly one ending square.
8 * 	0 representing empty squares we can walk over.
9 * 	-1 representing obstacles that we cannot walk over.
10 * 
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 * <img alt="" src="https://assets.leetcode.com/uploads/2021/08/02/lc-unique1.jpg" style="width: 324px; height: 245px;" />
15 * Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
16 * Output: 2
17 * Explanation: We have the following two paths: 
18 * 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
19 * 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
20 * 
21 * Example 2:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2021/08/02/lc-unique2.jpg" style="width: 324px; height: 245px;" />
23 * Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
24 * Output: 4
25 * Explanation: We have the following four paths: 
26 * 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)
27 * 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)
28 * 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)
29 * 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)
30 * 
31 * Example 3:
32 * <img alt="" src="https://assets.leetcode.com/uploads/2021/08/02/lc-unique3-.jpg" style="width: 164px; height: 165px;" />
33 * Input: grid = [[0,1],[2,0]]
34 * Output: 0
35 * Explanation: There is no path that walks over every empty square exactly once.
36 * Note that the starting and ending square can be anywhere in the grid.
37 * 
38 *  
39 * Constraints:
40 * 
41 * 	m == grid.length
42 * 	n == grid[i].length
43 * 	1 <= m, n <= 20
44 * 	1 <= m * n <= 20
45 * 	-1 <= grid[i][j] <= 2
46 * 	There is exactly one starting cell and one ending cell.
47 * 
48 */
49pub struct Solution {}
50
51// problem: https://leetcode.com/problems/unique-paths-iii/
52// discuss: https://leetcode.com/problems/unique-paths-iii/discuss/?currentPage=1&orderBy=most_votes&query=
53
54// submission codes start here
55
56impl Solution {
57    pub fn unique_paths_iii(grid: Vec<Vec<i32>>) -> i32 {
58        0
59    }
60}
61
62// submission codes end
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn test_980() {
70    }
71}
72