P4136 谁能赢呢？

标签：格子 Alice 奇偶性 Bob 棋盘 输入 P4136

题目描述

小明和小红经常玩一个博弈游戏。给定一个 n×n 的棋盘，一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合，选手只能把石头向上，下，左，右四个方向移动一格，并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。

假如小明先移动石头，而且两个选手都以最优策略走步，问最后谁能赢？

输入格式

输入文件有多组数据。

输入第一行包含一个整数 n，表示棋盘的规模。

当输入 n 为 0时，表示输入结束。

输出格式

对于每组数据，如果小明最后能赢，则输出 Alice，否则输出 Bob，每一组答案独占一行。

输入输出样例

输入 #1

2
0

输出 #1

Alice

说明/提示

对于 20%的数据，保证 1≤n≤10

对于 40% 的数据，保证 1≤n≤1000

对于 100%数据，保证 1≤n≤10000

思路

这题我看到的第一感觉，就是这个答案肯定和n有关系（准确的说是棋盘的格子数），因为Alice走一步，Bob再走一步，假设他们一定会把棋盘下满，那么总格子数的奇偶性就很重要了，如果总格子数是奇数，那Bob必胜，否则Alice必胜，脑海里构思一个2*2的地图就可以确定了

那么接下来要确定自己这个思想是否正确，画一个图

刚刚的假设中的情况：（蓝色是Alice，红色是Bob

可以看见最后红色没有移动空间，蓝赢

关于棋盘没下满的情况，可以这样子想：

除去起点这一行，你想截断棋盘至少往外再扩两行， 那么也就是把原本4*4的棋盘割成4*3罢了，格子总数依旧是偶数不变（偶偶得偶，奇偶得偶）

如果n是奇数，假设n是5，5*5=25，截断后变成5*3=15，奇偶性不变，完全可以全部看成把棋盘下满的情况

那么这题的代码就很容易了，就是判断n的奇偶性就行

代码

#include<iostream>
using namespace std;
int main(){
    int n;
    while(cin>>n&&n){
        if(n%2==0) cout<<"Alice"<<endl;
        else cout<<"Bob"<<endl;
    }
    return 0;
}

 

 

 

标签：格子,Alice,奇偶性,Bob,棋盘,输入,P4136
From： https://www.cnblogs.com/Ghost1GM/p/17566639.html