leetcode1728. 猫和老鼠 II（分析三——算法部分2）

leetcode1728. 猫和老鼠 II（分析三——算法部分2）

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

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

class Solution {
    int memo[9][9][9][9][3];
    pair food;
    pair mouse;
    pair cat;
    int mouseJump;
    int catJump;
    vector grid;
public:
    bool canMouseWin(vector& 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 q;
        
        for(int i=0;i2000)   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> findAllAdjacents(int mx,int my,int cx,int cy,int t){//逆推
        vector> adjacents;
        int rows=grid.size();
        int cols=grid[0].size();
        auto dir = vector>({{1,0},{-1,0},{0,1},{0,-1}});
        if(t==1){//如果该轮为老鼠轮，我们必须按照猫的步伐来推，则猫动
            for(int k=0;k<4;k++){//四个方向
                for(int d=0;d=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=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>({{1,0},{-1,0},{0,1},{0,-1}});

        if(t==1){
            for(int k=0;k<4;k++){//四个方向
                for(int d=0;d=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=rows || cy1<0 || cy1>=cols)  continue;//判断是否越界
                    if(grid[cx1][cy1]=='#') break;//不能碰壁
                    if(memo[mx][my][cx1][cy1][1]!=1)    return false;
                }
            }
        }

        return true;     
    }
};