[数据结构与算法]leetcode1728. 猫和老鼠 II（分析三——算法部分2）

最终可能的状态：
1.猫先到达食物
2.猫先到达老鼠
3.老鼠先到达食物
4.老鼠和猫都到不了食物，且猫也在1000回合内抓不到老鼠（设想一种情形：食物被墙挡住了，猫和老鼠谁也到达不了，二者以相同的速度兜圈圈）

由于最终可能的状态是确定的，我们可以用最终结果来反推。`

class Solution {
    int memo[9][9][9][9][3];
    pair<int,int> food;
    pair<int,int> mouse;
    pair<int,int> cat;
    int mouseJump;
    int catJump;
    vector<string> grid;
public:
    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
        int rows=grid.size();
        int cols=grid[0].size();
        this->catJump=mouseJump;
        this->mouseJump=catJump;
        this->grid=grid;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(grid[i][j]=='F') food={i,j};
                if(grid[i][j]=='M') mouse={i,j};
                if(grid[i][j]=='C') cat={i,j};

            }
        }
        queue<array<int,5>> q;
        
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++)
                for(int t=1;t<=2;t++){//不论是轮到猫还是鼠
                if(grid[i][j]=='#') continue;
                if(i==food.first && j==food.second)    continue;// 排除掉老鼠、猫、食物三者在同一位置
                memo[i][j][food.first][food.second][t]=2;//1.猫先到食物，猫赢
                memo[food.first][food.second][i][j][t]=1;// 2.老鼠先到食物，老鼠赢
                q.push({i,j,food.first,food.second,t});
                q.push({food.first,food.second,i,j,t});
            }
        }

        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++)
                for(int t=1;t<=2;t++){//不论是轮到猫还是鼠
                if(grid[i][j]=='#') continue;
                memo[i][j][i][j][t]=2;//3.猫鼠在同一位置，猫赢
                q.push({i,j,i,j,t});
            }
        }

        int step=0;
        while(!q.empty()){
            step++;
            if(step>2000)   return false;
            int len=q.size();
            while(len--){
                int mx=q.front()[0];
                int my=q.front()[1];
                int cx=q.front()[2];
                int cy=q.front()[3];
                int t=q.front()[4];
                
                int status=memo[mx][my][cx][cy][t];//status表示该状态对应的输赢结果，输赢结果上面已经存在了memo里面

                q.pop();

                for(auto next:findAllAdjacents(mx,my,cx,cy,t)){//考虑所有上一层邻接结点
                    int mx1=next[0];
                    int my1=next[1];
                    int cx1=next[2];
                    int cy1=next[3];
                    int t1=next[4];

                    if(memo[mx1][my1][cx1][cy1][t1]!=0) continue;

                    if(t1==status){
                        //比如，轮到猫走，memo是鼠必败（猫赢）；或者，轮到鼠走，memo是猫必败（鼠赢）
                        //t1取值有1,2。1表示轮到鼠，2表述轮到猫
                        //status取值有1,2,3。1表示鼠赢，2表示猫赢,3表示和棋

                        memo[mx1][my1][cx1][cy1][t1]=status;
                        q.push({mx1,my1,cx1,cy1,t1});
                    }
                    else if(allAdjacentsWin(mx1,my1,cx1,cy1,t1)){
                        //不能判断出必赢，那么考虑是否必败
                        //考虑其对手轮次，即下一层邻接结点是必赢还是必输

                        memo[mx1][my1][cx1][cy1][t1]=(t1==1)?2:1;//t1和status一定一个是1，另一个就是2
                        q.push({mx1,my1,cx1,cy1,t1});
                    }
                }
            }
        }

        return memo[mouse.first][mouse.second][cat.first][cat.second][1] == 1;//回到初始态，轮到老鼠走且老鼠必赢则返回true
    }
    

    vector<array<int,5>> findAllAdjacents(int mx,int my,int cx,int cy,int t){//逆推
        vector<array<int,5>> adjacents;
        int rows=grid.size();
        int cols=grid[0].size();
        auto dir = vector<pair<int,int>>({{1,0},{-1,0},{0,1},{0,-1}});
        if(t==1){//如果该轮为老鼠轮，我们必须按照猫的步伐来推，则猫动
            for(int k=0;k<4;k++){//四个方向
                for(int d=0;d<catJump;d++){
                    int cx1=cx+dir[k].first*d;
                    int cy1=cy+dir[k].second*d;
                    if(cx1<0 || cx1>=rows || cy1<0 || cy1>=cols)  continue;//判断是否越界
                    if(grid[cx1][cy1]=='#') break;//不能碰壁
                    adjacents.push_back({mx,my,cx1,cy1,2});
                }
            }
        }

        if(t==2){//如果该轮为猫轮，我们必须按照鼠的步伐来推，则鼠动
            for(int k=0;k<4;k++){//四个方向
                for(int d=0;d<mouseJump;d++){
                    int mx1=mx+dir[k].first*d;
                    int my1=my+dir[k].second*d;
                    if(mx1<0 || mx1>=rows || my1<0 || my1>=cols)  continue;//判断是否越界
                    if(grid[mx1][my1]=='#') break;//不能碰壁
                    adjacents.push_back({mx1,my1,cx,cy,1});
                }
            }
        }
        return adjacents;
    }


    bool allAdjacentsWin(int mx,int my,int cx,int cy,int t){//正推
        int rows=grid.size();
        int cols=grid[0].size();
        auto dir = vector<pair<int,int>>({{1,0},{-1,0},{0,1},{0,-1}});

        if(t==1){
            for(int k=0;k<4;k++){//四个方向
                for(int d=0;d<mouseJump;d++){
                    int mx1=mx+dir[k].first*d;
                    int my1=my+dir[k].second*d;
                    if(mx1<0 || mx1>=rows || my1<0 || my1>=cols)  continue;//判断是否越界
                    if(grid[mx1][my1]=='#') break;//不能碰壁
                    if(memo[mx1][my1][cx][cy][2]!=2)    return false;
                }
            }
        }
        
        
        if(t==2){
            for(int k=0;k<4;k++){//四个方向
                for(int d=0;d<catJump;d++){
                    int cx1=cx+dir[k].first*d;
                    int cy1=cy+dir[k].second*d;
                    if(cx1<0 || cx1>=rows || cy1<0 || cy1>=cols)  continue;//判断是否越界
                    if(grid[cx1][cy1]=='#') break;//不能碰壁
                    if(memo[mx][my][cx1][cy1][1]!=1)    return false;
                }
            }
        }

        return true;     
    }
};