T3

hmh13951417981 · 2024-03-23 18:47:36 · 题解

从（1,1）开始走，轮流移动，每次只能上移、右移、右上移，移动到（m,n）位置的人获胜。

类似小时候玩过的一种报数游戏，每次轮流往上加1~3，谁恰好报到30获胜。

这种简单博弈类游戏，需要从最终获胜状态往前推状态。

对手可以一步走到必位置 就是必败位置。

对手只能走到必败位置，就是必胜位置。

因为（m,n）这个点为必胜位置，那么（m-1,n），(m-1,n-1)，(m,n-1)这三个点都是必败位置 （如果我们走到，对手下一步就能胜利）。

因为（m-1，n）这个位置为必败位置，（m-2,n）这个位置就是必胜位置（对手只能走到必败位置）。

用点代替必胜位置，×代替必败位置，可如此类推。

观察得：横纵坐标与终点奇偶性均相同的点为必胜点，其余为必败点。

我们如果初始位置在必胜点，我们只能走到必败点。

反之，总能会有一个方向走到必胜点。

#include<bits/stdc++.h>
using namespace std; 
long long t,n,m;
int main()
{   scanf("%ld",&t);
    while(t--){
        scanf("%ld%ld",&n,&m);
        if(n&1){
            if(m&1) printf("-1\n");//必败
            else printf("1\n");//向右调整横坐标
        }
        else{
            if(m&1) printf("2\n");//向上调整纵坐标
            else printf("3\n");//向右上调整横纵坐标
        }
    }
    return 0;
}