<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>

struct Point {

    int y;
    int x;

    bool operator==(Point const& other) const {

        return this->x == other.x && this->y == other.y;
    }
};

namespace std {

    template<>
    struct hash<Point>
    {
        std::size_t operator()(const Point& p) const noexcept
        {
            std::size_t h1 = std::hash<int>{}(p.x);
            std::size_t h2 = std::hash<int>{}(p.y);
            return h1 ^ (h2 << 1);
        }
    };

}

enum class Player {
    CAT,
    MOUSE
};

struct State {

    Point m;
    Point c;
    Player turn;
};

struct Result {

    Player player;
    int count;
};


class Solution {
public:
    bool canMouseWin(std::vector<std::string>& grid, int catJump, int mouseJump) {

        grid_ = std::move(grid);
        cj = catJump;
        mj = mouseJump;
        rows = grid_.size();
        assert(rows > 0);

        cols = grid_[0].size();
        assert(cols > 0);
        
        for (int i = 0; i < rows; ++i) {

            for (int j = 0; j < cols; ++j) {


                if (grid_[i][j] == 'C') {

                    cat_start = { i, j };
                }
                else if (grid_[i][j] == 'M') {

                    mouse_start = { i, j };
                }
                else if (grid_[i][j] == 'F') {

                    food_pos = { i, j };
                }

            }

        }

        std::queue<State> states = fillInitialStates();


        while ( !states.empty() ) {


            State state = states.front();
            states.pop();

            assert( hasResult(state) );

            std::vector<State> prev_states = getPrevStates(state);

            for (const State& prev_state : prev_states) {

                assert( !hasResult(prev_state) );
                updateState(prev_state, state);

                if (hasResult(prev_state)) {
                    states.push(prev_state);
                }
            }

        }

        State start = { mouse_start, cat_start, Player::MOUSE };

        if ( hasResult(start) && getResult(start).player == Player::MOUSE && getResult(start).count <= 1000) {
            return true;
        }
        else {
            return false;
        }

    }

private:

    std::queue<State> fillInitialStates() {
    
        std::queue<State> states;

        for (int i = 0; i < rows; ++i) {

            for (int j = 0; j < cols; ++j) {

                if (grid_[i][j] != '#' && grid_[i][j] != 'F') {

                    states.push( State{ Point{i,j}, food_pos, Player::MOUSE } );

                    setResult(State{ Point{i,j}, food_pos, Player::MOUSE }, Result{ Player::CAT, 0 });
                  

                    states.push( State{ food_pos, Point{i,j}, Player::CAT } );
                    
                    setResult(State{ food_pos, Point{i,j}, Player::CAT }, Result{ Player::MOUSE, 0 });


                    states.push( State{ Point{i,j}, Point{i,j}, Player::MOUSE } );
                    
                    setResult( State{ Point{i,j}, Point{i,j}, Player::MOUSE }, { Player::CAT, 0 } );
                   
                    states.push( State{ Point{i,j}, Point{i,j}, Player::CAT } );  

                    setResult( State{ Point{i,j}, Point{i,j}, Player::CAT }, Result{ Player::CAT, 0 } );
                }
            }
        }

        return states;
    };

    std::vector<State> getPrevStates(const State& state) {

        std::vector<State> prev_states;

        if ( state.turn == Player::MOUSE ) {

            Point cat_pos = state.c;

            int i = 1;
            while (i <= cj) {

                Point new_pos = cat_pos;
                new_pos.x += i;

                if (isValidPos(new_pos) && canGo(new_pos) ) {

                    State new_state = { state.m, new_pos, Player::CAT };

                    if ( !hasResult( new_state ) ) {
                        prev_states.push_back( new_state );
                    }

                }
                else {
                    break;
                }

                ++i;
            }

            i = 1;

            while (i <= cj) {

                Point new_pos = cat_pos;
                new_pos.x -= i;

                if (isValidPos(new_pos) && canGo(new_pos)) {

                    State new_state = { state.m, new_pos, Player::CAT };

                    if (!hasResult(new_state)) {
                        prev_states.push_back(new_state);
                    }

                }
                else {
                    break;
                }

                ++i;
            }

            i = 1;

            while (i <= cj) {

                Point new_pos = cat_pos;
                new_pos.y += i;

                if (isValidPos(new_pos) && canGo(new_pos)) {

                    State new_state = { state.m, new_pos, Player::CAT };

                    if (!hasResult(new_state)) {
                        prev_states.push_back(new_state);
                    }

                }
                else {
                    break;
                }

                ++i;
            }

            i = 1;

            while (i <= cj) {

                Point new_pos = cat_pos;
                new_pos.y -= i;

                if (isValidPos(new_pos) && canGo(new_pos)) {

                    State new_state = { state.m, new_pos, Player::CAT };

                    if (!hasResult(new_state)) {
                        prev_states.push_back(new_state);
                    }

                }
                else {
                    break;
                }

                ++i;
            }

            State new_state = { state.m, state.c, Player::CAT };

            if ( !hasResult(new_state) ) {
                prev_states.push_back(new_state);
            }

        }

        else {

            Point mouse_pos = state.m;

            int i = 1;
            while (i <= mj) {

                Point new_pos = mouse_pos;
                new_pos.x += i;

                if ( isValidPos(new_pos) && canGo(new_pos) ) {

                    State new_state = { new_pos, state.c, Player::MOUSE };

                    if (!hasResult(new_state)) {
                        prev_states.push_back(new_state);
                    }

                }
                else {
                    break;
                }

                ++i;
            }

            i = 1;

            while (i <= mj) {

                Point new_pos = mouse_pos;
                new_pos.x -= i;

                if (isValidPos(new_pos) && canGo(new_pos)) {

                    State new_state = { new_pos, state.c, Player::MOUSE };

                    if (!hasResult(new_state)) {
                        prev_states.push_back(new_state);
                    }

                }
                else {
                    break;
                }

                ++i;
            }

            i = 1;

            while (i <= mj) {

                Point new_pos = mouse_pos;
                new_pos.y += i;

                if (isValidPos(new_pos) && canGo(new_pos)) {

                    State new_state = { new_pos, state.c, Player::MOUSE };

                    if (!hasResult(new_state)) {
                        prev_states.push_back(new_state);
                    }

                }
                else {
                    break;
                }

                ++i;
            }

            i = 1;

            while (i <= mj) {

                Point new_pos = mouse_pos;
                new_pos.y -= i;

                if (isValidPos(new_pos) && canGo(new_pos)) {

                    State new_state = { new_pos, state.c, Player::MOUSE };

                    if (!hasResult(new_state)) {
                        prev_states.push_back(new_state);
                    }

                }
                else {
                    break;
                }

                ++i;
            }

            State new_state = { state.m, state.c, Player::MOUSE };

            if (!hasResult(new_state)) {
                prev_states.push_back(new_state);
            }



        }

        return prev_states;

    }

    std::vector<State> getNextStates(const State& state) {


        std::vector<State> next_states;

        if (state.turn == Player::MOUSE) {

            Point mouse_pos = state.m;

            int i = 1;
            while (i <= mj) {

                Point new_pos = mouse_pos;
                new_pos.x += i;

                if (isValidPos(new_pos) && canGo(new_pos)) {

                    State new_state = { new_pos, state.c, Player::CAT };
                    
                    next_states.push_back(new_state);
                    
                }
                else {
                    break;
                }

                ++i;
            }

            i = 1;

            while (i <= mj) {

                Point new_pos = mouse_pos;
                new_pos.x -= i;

                if ( isValidPos(new_pos) && canGo(new_pos) ) {

                    State new_state = { new_pos, state.c, Player::CAT };
                    next_states.push_back(new_state);
                }
                else {
                    break;
                }

                ++i;
            }

            i = 1;

            while (i <= mj) {

                Point new_pos = mouse_pos;
                new_pos.y += i;

                if (isValidPos(new_pos) && canGo(new_pos)) {

                    State new_state = { new_pos, state.c, Player::CAT };
                    next_states.push_back(new_state);

                }
                else {
                    break;
                }

                ++i;
            }

            i = 1;

            while (i <= mj) {

                Point new_pos = mouse_pos;
                new_pos.y -= i;

                if (isValidPos(new_pos) && canGo(new_pos) ) {

                    State new_state = { new_pos, state.c, Player::CAT };
                    next_states.push_back(new_state);

                }
                else {
                    break;
                }

                ++i;
            }

            State new_state = { state.m, state.c, Player::CAT };

            next_states.push_back(new_state);
        }

        else {

            Point cat_pos = state.c;

            int i = 1;
            while (i <= cj) {

                Point new_pos = cat_pos;
                new_pos.x += i;

                if (isValidPos(new_pos) && canGo(new_pos)) {

                    State new_state = { state.m, new_pos, Player::MOUSE };
                    next_states.push_back( new_state );
                   
                }
                else {
                    break;
                }

                ++i;
            }

            i = 1;

            while (i <= cj) {

                Point new_pos = cat_pos;
                new_pos.x -= i;

                if (isValidPos(new_pos) && canGo(new_pos)) {

                    State new_state = { state.m, new_pos, Player::MOUSE };
                    next_states.push_back(new_state);

                }
                else {
                    break;
                }

                ++i;
            }

            i = 1;

            while (i <= cj) {

                Point new_pos = cat_pos;
                new_pos.y += i;

                if (isValidPos(new_pos) && canGo(new_pos)) {

                    State new_state = { state.m, new_pos, Player::MOUSE };
                    next_states.push_back(new_state);

                }
                else {
                    break;
                }

                ++i;
            }

            i = 1;

            while (i <= cj) {

                Point new_pos = cat_pos;
                new_pos.y -= i;

                if (isValidPos(new_pos) && canGo(new_pos)) {

                    State new_state = { state.m, new_pos, Player::MOUSE };
                    next_states.push_back(new_state);

                }
                else {
                    break;
                }

                ++i;
            }

            State new_state = { state.m, state.c, Player::MOUSE };
            next_states.push_back(new_state);            
        }

        return next_states;
    }


    void updateState(const State& prev_state, const State& state) {

        assert( hasResult(state) );

        if (state.turn == Player::MOUSE) {

            assert(prev_state.turn == Player::CAT);

            Result result = getResult(state);

            if (result.player == Player::CAT) {

                setResult(prev_state, Result{ Player::CAT , result.count + 1 } );
            }
            else {

                std::vector<State> next_states = getNextStates(prev_state);

                bool all_losing = true;
                int cat_max_count = 0;

                for (const State& next_state : next_states) {


                    if (!hasResult(next_state)) {
                        all_losing = false;
                        break;
                    }
                    else {

                        Result next_result = getResult(next_state);

                        if (next_result.player == Player::CAT) {
                            all_losing = false;
                            break;
                        }

                      //  assert(next_result.player == Player::MOUSE);
                        cat_max_count = std::max(cat_max_count, next_result.count);
                    }

                }

                if (all_losing) {

                    setResult(prev_state, Result{Player::MOUSE, cat_max_count + 1 } );
                }


            }
        }
        else {


            Result result = getResult(state);

            if (result.player == Player::MOUSE) {

                setResult(prev_state, Result{ Player::MOUSE , result.count + 1 });
            }
            else {

                std::vector<State> next_states = getNextStates(prev_state);

                bool all_losing = true;
                int mouse_max_count = 0;

                for (const State& next_state : next_states) {

                    if (!hasResult(next_state)) {
                        all_losing = false;
                        break;
                    }
                    else {

                        Result next_result = getResult(next_state);
                        //assert(next_result.player == Player::CAT);

                        if (next_result.player == Player::MOUSE) {
                            all_losing = false;
                            break;
                        }

                        mouse_max_count = std::max( mouse_max_count, next_result.count );
                    }

                }

                if (all_losing) {

                    setResult(prev_state, Result{ Player::CAT, mouse_max_count + 1 });
                }


            }


        }

    }


    bool isValidPos(const Point& pos) {

        return pos.y >= 0 && pos.y < rows && pos.x >= 0 && pos.x < cols;
    }

    bool canGo(const Point& pos) {

        return grid_[pos.y][pos.x] != '#';
    }


    bool hasResult( const State& state ) {

        if (state.turn == Player::CAT) {

            if ( dp_cat.count(state.m) && dp_cat[state.m].count(state.c) ) {
                return true;
            }
            else {
                return false;
            }
        }
        else {
            if (dp_mouse.count(state.m) && dp_mouse[state.m].count(state.c)) {
                return true;
            }
            else {
                return false;
            }
        }
    }


    Result getResult(const State& state) {

        if (state.turn == Player::CAT) {

            return dp_cat[state.m][state.c];
        }
        else {
            return dp_mouse[state.m][state.c];
        }
    }

    void setResult(const State& state, const Result& result) {

   //     std::cout << state.m.y << " : " << state.m.x << " | " << state.c.y << " : " << state.c.x << " | "
   //         << (state.turn == Player::CAT ? "CAT" : "MOUSE") << " | " << (result.player == Player::CAT ? "CAT" : "MOUSE") << std::endl;

        if (state.turn == Player::CAT) {

            dp_cat[state.m][state.c] = result;
        }
        else {
            dp_mouse[state.m][state.c] = result;
        }
    }



    std::vector<std::string> grid_;

    int cj;
    int mj;
    
    int rows, cols;
    
    Point cat_start, mouse_start, food_pos;

    std::unordered_map< Point, std::unordered_map<Point, Result> > dp_mouse, dp_cat;

};
92200