1728. Cat and Mouse II Hard

1/**
2 * [1728] Cat and Mouse II
3 *
4 * A game is played by a cat and a mouse named Cat and Mouse.
5 * The environment is represented by a grid of size rows x cols, where each element is a wall, floor, player (Cat, Mouse), or food.
6 * 
7 * 	Players are represented by the characters 'C'(Cat),'M'(Mouse).
8 * 	Floors are represented by the character '.' and can be walked on.
9 * 	Walls are represented by the character '#' and cannot be walked on.
10 * 	Food is represented by the character 'F' and can be walked on.
11 * 	There is only one of each character 'C', 'M', and 'F' in grid.
12 * 
13 * Mouse and Cat play according to the following rules:
14 * 
15 * 	Mouse moves first, then they take turns to move.
16 * 	During each turn, Cat and Mouse can jump in one of the four directions (left, right, up, down). They cannot jump over the wall nor outside of the grid.
17 * 	catJump, mouseJump are the maximum lengths Cat and Mouse can jump at a time, respectively. Cat and Mouse can jump less than the maximum length.
18 * 	Staying in the same position is allowed.
19 * 	Mouse can jump over Cat.
20 * 
21 * The game can end in 4 ways:
22 * 
23 * 	If Cat occupies the same position as Mouse, Cat wins.
24 * 	If Cat reaches the food first, Cat wins.
25 * 	If Mouse reaches the food first, Mouse wins.
26 * 	If Mouse cannot get to the food within 1000 turns, Cat wins.
27 * 
28 * Given a rows x cols matrix grid and two integers catJump and mouseJump, return true if Mouse can win the game if both Cat and Mouse play optimally, otherwise return false.
29 *  
30 * Example 1:
31 * <img alt="" src="https://assets.leetcode.com/uploads/2020/09/12/sample_111_1955.png" style="width: 580px; height: 239px;" />
32 * Input: grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2
33 * Output: true
34 * Explanation: Cat cannot catch Mouse on its turn nor can it get the food before Mouse.
35 * 
36 * Example 2:
37 * <img alt="" src="https://assets.leetcode.com/uploads/2020/09/12/sample_2_1955.png" style="width: 580px; height: 175px;" />
38 * Input: grid = ["M.C...F"], catJump = 1, mouseJump = 4
39 * Output: true
40 * 
41 * Example 3:
42 * 
43 * Input: grid = ["M.C...F"], catJump = 1, mouseJump = 3
44 * Output: false
45 * 
46 *  
47 * Constraints:
48 * 
49 * 	rows == grid.length
50 * 	cols = grid[i].length
51 * 	1 <= rows, cols <= 8
52 * 	grid[i][j] consist only of characters 'C', 'M', 'F', '.', and '#'.
53 * 	There is only one of each character 'C', 'M', and 'F' in grid.
54 * 	1 <= catJump, mouseJump <= 8
55 * 
56 */
57pub struct Solution {}
58
59// problem: https://leetcode.com/problems/cat-and-mouse-ii/
60// discuss: https://leetcode.com/problems/cat-and-mouse-ii/discuss/?currentPage=1&orderBy=most_votes&query=
61
62// submission codes start here
63
64impl Solution {
65    pub fn can_mouse_win(grid: Vec<String>, cat_jump: i32, mouse_jump: i32) -> bool {
66        false
67    }
68}
69
70// submission codes end
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn test_1728() {
78    }
79}
80