作业帮一个N*M的棋盘,右下方有一个棋子,两人轮流走,可以走到上下左右相邻的未走过的格子,不能走则输,谁胜?棋盘格子为奇数则后手胜(1*1 后手直接胜)棋盘格子为偶数则先手胜(1*2 先手走一步就胜)
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/13 00:22:04
一个N*M的棋盘,右下方有一个棋子,两人轮流走,可以走到上下左右相邻的未走过的格子,不能走则输,谁胜?棋盘格子为奇数则后手胜(1*1 后手直接胜)棋盘格子为偶数则先手胜(1*2 先手走一步就胜)
一个N*M的棋盘,右下方有一个棋子,两人轮流走,可以走到上下左右相邻的未走过的格子,不能走则输,谁胜?
棋盘格子为奇数则后手胜(1*1 后手直接胜)
棋盘格子为偶数则先手胜(1*2 先手走一步就胜)
求详细证明.
有可能走不完棋盘啊，补充下 这两人的智商足够高
一个N*M的棋盘,右下方有一个棋子,两人轮流走,可以走到上下左右相邻的未走过的格子,不能走则输,谁胜?棋盘格子为奇数则后手胜(1*1 后手直接胜)棋盘格子为偶数则先手胜(1*2 先手走一步就胜)
这是棋盘对弈的问题,可使用配对解法
N*M定义为N行M列
若棋盘格子为奇数,则N和M均为奇数.设为N*M=2k+1
右下方的棋子已占一个格,还剩下2k个格子.其中最下面一行有M-1个格子,为偶数,剩下N-1行,为偶数
因此,可以把剩下的2k个格子两两配对分成k个1×2的小矩形
这时,先手总是领先进入某一个1×2小矩形的第一个格,后手总可以随之进入这个小矩形的第二个格.最后必然先手先无法移动这个棋子,先手输．后手必取胜
若棋盘格子为偶数,设为N*M=2k
将这2k个格子两两配对分成k个1×2的小矩形
右下方的棋子必在某个1×2的小矩形的一个格子中.先手将棋子走入这个1×2的小矩形的另一个格子中．这时还有k-1个1×2的小矩形,每个小矩形中都有两个小方格．这时该后手走,后手总是领先进入剩下的某个1×2小矩形的第一个格,先手就可以随之进入这个小矩形的第二个格.最后必然后手先无法移动这个棋子,后手输．先手必取胜
所以
棋盘格子为奇数则后手胜
棋盘格子为偶数则先手胜
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
注：将棋盘格子两两配对成为若干个1×2的小矩形是解决本题的关键!
有什么不懂的再Hi我吧
思考中 ，确实有难度
棋盘格子怎么会出现奇数呢？N*M只能是偶数
n为正整数
先手=2n+1，为奇数。
后手=2n，为偶数。
“N*M只能是偶数”这位仁兄，我们的围棋棋盘是361啊
当M和N同为奇数时，其积一定是奇数
没有走不完的棋盘，只有不想走的人。愚公可以搬走山的。