<p>A game is played by a cat and a mouse named Cat and Mouse.</p>

<p>The environment is represented by a <code>grid</code> of size <code>rows x cols</code>, where each element is a wall, floor, player (Cat, Mouse), or food.</p>

<ul>
	<li>Players are represented by the characters <code>&#39;C&#39;</code>(Cat)<code>,&#39;M&#39;</code>(Mouse).</li>
	<li>Floors are represented by the character <code>&#39;.&#39;</code> and can be walked on.</li>
	<li>Walls are represented by the character <code>&#39;#&#39;</code> and cannot be walked on.</li>
	<li>Food is represented by the character <code>&#39;F&#39;</code> and can be walked on.</li>
	<li>There is only one of each character <code>&#39;C&#39;</code>, <code>&#39;M&#39;</code>, and <code>&#39;F&#39;</code> in <code>grid</code>.</li>
</ul>

<p>Mouse and Cat play according to the following rules:</p>

<ul>
	<li>Mouse <strong>moves first</strong>, then they take turns to move.</li>
	<li>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 <code>grid</code>.</li>
	<li><code>catJump, mouseJump</code> are the maximum lengths Cat and Mouse can jump at a time, respectively. Cat and Mouse can jump less than the maximum length.</li>
	<li>Staying in the same position is allowed.</li>
	<li>Mouse can jump over Cat.</li>
</ul>

<p>The game can end in 4 ways:</p>

<ul>
	<li>If Cat occupies the same position as Mouse, Cat wins.</li>
	<li>If Cat reaches the food first, Cat wins.</li>
	<li>If Mouse reaches the food first, Mouse wins.</li>
	<li>If Mouse cannot get to the food within 1000 turns, Cat wins.</li>
</ul>

<p>Given a <code>rows x cols</code> matrix <code>grid</code> and two integers <code>catJump</code> and <code>mouseJump</code>, return <code>true</code><em> if Mouse can win the game if both Cat and Mouse play optimally, otherwise return </em><code>false</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/12/sample_111_1955.png" style="width: 580px; height: 239px;" />
<pre>
<strong>Input:</strong> grid = [&quot;####F&quot;,&quot;#C...&quot;,&quot;M....&quot;], catJump = 1, mouseJump = 2
<strong>Output:</strong> true
<strong>Explanation:</strong> Cat cannot catch Mouse on its turn nor can it get the food before Mouse.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/12/sample_2_1955.png" style="width: 580px; height: 175px;" />
<pre>
<strong>Input:</strong> grid = [&quot;M.C...F&quot;], catJump = 1, mouseJump = 4
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> grid = [&quot;M.C...F&quot;], catJump = 1, mouseJump = 3
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>rows == grid.length</code></li>
	<li><code>cols = grid[i].length</code></li>
	<li><code>1 &lt;= rows, cols &lt;= 8</code></li>
	<li><code>grid[i][j]</code> consist only of characters <code>&#39;C&#39;</code>, <code>&#39;M&#39;</code>, <code>&#39;F&#39;</code>, <code>&#39;.&#39;</code>, and <code>&#39;#&#39;</code>.</li>
	<li>There is only one of each character <code>&#39;C&#39;</code>, <code>&#39;M&#39;</code>, and <code>&#39;F&#39;</code> in <code>grid</code>.</li>
	<li><code>1 &lt;= catJump, mouseJump &lt;= 8</code></li>
</ul>

#define printf(...) (0)

class Solution {
public:
    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
        int m = grid.size(), n = grid[0].size();

        int state_mark[8][8][8][8][3] {};
        int opposite_win_cnt[8][8][8][8][3] {};

        using State = tuple<int, int, int, int, int>;

        queue<State> q;

        auto state_mark_ref = [&](const State& curr) -> int & {
            auto [i1, j1, i2, j2, t] = curr;
            return state_mark[i1][j1][i2][j2][t];
        };
        
        auto opposite_win_cnt_ref = [&](const State& curr) -> int & {
            auto [i1, j1, i2, j2, t] = curr;
            return opposite_win_cnt[i1][j1][i2][j2][t];
        };

        auto printstate = [](const State& state) {
            auto [i1, i2, j1, j2, t] = state;
            printf("(%d, %d, %d, %d, %d)", i1, i2, j1, j2, t);
        };

        auto mark = [&](const State& curr, int res) {
            if (state_mark_ref(curr) == 0) {
                state_mark_ref(curr) = res;
                q.emplace(curr);
                printf("mark state ");
                printstate(curr);
                printf(" as %d\n", res);
            }
        };

        int mouse_init_i = INT_MIN, mouse_init_j = INT_MIN, cat_init_i = INT_MIN, cat_init_j = INT_MIN;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'F') {
                    for (int oi = 0; oi < m; ++oi) {
                        for (int oj = 0; oj < n; ++oj) {
                            if (i == oi && j == oj) {
                                continue;
                            }
                            mark({i, j, oi, oj, 1}, 1);
                            mark({i, j, oi, oj, 2}, 1);
                            mark({oi, oj, i, j, 1}, 2);
                            mark({oi, oj, i, j, 2}, 2);
                        }
                    }
                } else if (grid[i][j] != '#') {
                    mark({i, j, i, j, 1}, 2);
                    mark({i, j, i, j, 2}, 2);
                }
                if (grid[i][j] == 'M') {
                    mouse_init_i = i;
                    mouse_init_j = j;
                }
                if (grid[i][j] == 'C') {
                    cat_init_i = i;
                    cat_init_j = j;
                }
            }
        }

        printf("init mark done\n");

        auto in_range = [&](int i, int j) {
            return i >= 0 && i < m && j >= 0 && j < n;
        };

        auto do_get_prev_states = [&](const State& curr) {
            // printf("do_get_prev_states on ");
            // printstate(curr);
            // printf("\n");
            auto [i1, j1, i2, j2, t] = curr;
            vector<State> prevs;
            int pt = t == 1 ? 2 : 1;
            prevs.emplace_back(i1, j1, i2, j2, pt);
            const vector<pair<int, int>> directions {
                { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }
            };
            if (pt == 1) {
                for (auto [dir_i, dir_j] : directions) {
                    for (int offset = 1; offset <= mouseJump; ++offset) {
                        int new_i = i1 + dir_i * offset, new_j = j1 + dir_j * offset;
                        // printf("new_i: %d; new_j: %d\n", new_i, new_j);
                        if (!in_range(new_i, new_j) || grid[new_i][new_j] == '#') {
                            break;
                        }
                        prevs.emplace_back(new_i, new_j, i2, j2, pt);
                    }
                }
            } else {
                for (auto [dir_i, dir_j] : directions) {
                    for (int offset = 1; offset <= catJump; ++offset) {
                        int new_i = i2 + dir_i * offset, new_j = j2 + dir_j * offset;
                        // printf("new_i: %d; new_j: %d\n", new_i, new_j);
                        if (!in_range(new_i, new_j) || grid[new_i][new_j] == '#') {
                            break;
                        }
                        prevs.emplace_back(i1, j1, new_i, new_j, pt);
                    }
                }
            }
            // printf("do_get_prev_states finish\n");
            // for (auto &prev : prevs) {
            //     printf("- ");
            //     printstate(prev);
            //     printf("\n");
            // }
            return prevs;
        };

        int prev_states_cnt_memo[8][8][8][8][3] {};

        auto get_next_states_cnt = [&](const State& curr) {
            auto [i1, j1, i2, j2, t] = curr;
            int opposite_t = t == 1 ? 2 : 1;
            int &cnt_ref = prev_states_cnt_memo[i1][j1][i2][j2][opposite_t];
            if (cnt_ref == 0) {
                // if set, cnt is always > 0
                auto prevs = do_get_prev_states({i1, j1, i2, j2, opposite_t});
                cnt_ref = prevs.size();
            }
            printf("get_prev_states_cnt on ");
            printstate(curr);
            printf(" | %d\n", cnt_ref);
            return cnt_ref;
        };

        auto get_prev_states = [&](const State& curr) {
            auto [i1, j1, i2, j2, t] = curr;
            auto ret = do_get_prev_states(curr);
            prev_states_cnt_memo[i1][j1][i2][j2][t] = ret.size();
            return ret;
        };

        // get_prev_states_cnt({ 2, 2, 2, 0, 1 });

        while (!q.empty()) {
            auto [i1, j1, i2, j2, t] = q.front();
            auto curr = q.front();
            auto curr_state_mark = state_mark_ref(curr);
            q.pop();

            printf("curr ");
            printstate(curr);
            printf(" with mark %d", curr_state_mark);
            printf("\n");

            auto prevs = get_prev_states(curr);
            // printf("get_prev_states done\n");
            for (const auto &prev : prevs) {
                printf("    prev ");
                printstate(prev);
                printf("\n");
                auto [pi1, pj1, pi2, pj2, pt] = prev;
                if (curr_state_mark == pt) {
                    mark(prev, curr_state_mark);
                } else {
                    ++opposite_win_cnt_ref(prev);
                    if (opposite_win_cnt_ref(prev) == get_next_states_cnt(prev)) {
                        mark(prev, curr_state_mark);
                    }
                }
            }
            printf("\n");
        }

        return state_mark_ref({ mouse_init_i, mouse_init_j, cat_init_i, cat_init_j, 1 }) == 1;
    }
};
138800