棋盘游戏......但不同
Chessboard game...but a different one
https://www.hackerrank.com/challenges/chessboard-game-again-1
上面的问题我试过下面的方式,但答案被评价为错误。(我不是在求解决方案,而是在问方法中的缺陷);
我的代码(请忽略c99错误)
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int numofmov = 0;
int issafe(int a,int b){
if(a>=0 && a<15 && b>=0 && b<15)
return 1;
return 0;
}
void move(int board[][15]){
for(int i=0;i<15;i++){
for(int j=0;j<15;j++){
if(board[i][j]>0){
board[i][j]--;
if(issafe(board,i-2,j+1)==1) {
numofmov++;
board[i-2][j+1]++;
}
if(issafe(board,i-2,j-1)==1) {
numofmov++;
board[i-2][j-1]++;
}
if(issafe(board,i+1,j-2)==1) {
numofmov++;
board[i+1][j-2]++;
}
if(issafe(board,i-1,j-2)==1) {
numofmov++;
board[i-1][j-2]++;
}
}
}
}
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int t;
scanf("%d",&t);
while(t--){
int k;
scanf("%d",&k);
int board[15][15];
for(int j=0;j<15;j++){
for(int h=0;h<15;h++){
board[j][h]=0;
}
}
for(int i=0;i<k;i++){
int x,y;
scanf("%d %d",&x,&y);
board[x-1][y-1]++;
}
int bro=0,mov=numofmov;
while(bro==0){
move(board);
if(numofmov==mov){
bro++;
printf("Second\n");
break;
}
mov = numofmov;
move(board);
if(numofmov==mov){
bro++;
printf("First\n");
break;
}
mov = numofmov;
}
}
return 0;
}
我的方法是继续使所有硬币的所有移动成为可能,直到我们到达无法移动的地步。但这在某些测试用例中给出了错误的答案。
您是在问这种方法有什么问题?
"My approach is to go on making all the moves possible for all the
coins until we come to a point when no moves are possible. But this is
giving wrong answers in some test cases."
我没有阅读您的代码,但我可以说主要问题是您的方法本身。您将此问题视为蛮力(制定所有可能的移动路径,看看谁赢了)。可能的移动数可以任意大,检查导致获胜的移动是无限慢的。实际上,它要么是动态规划,要么是更相关的博弈论问题。
这样想。起始位置是否唯一标识了这场比赛的获胜者?如果改变单个硬币的初始位置,获胜者是否也会改变?
解决此类问题的最佳方法是将其简化。 假设只有一个棋盘和一个硬币,位于 (x,y)
。现在请注意,每次将硬币从位置 (x,y)
移动到位置 (a,b)
后,以下内容为真 a+b<x+y
。因此,如果 (x,y)
是 (1,1),(1,2),(2,1),(2,2)
之一,则下棋的玩家已经输了。所以我的目标是确保我的对手从已经失去的位置开始行动,如果我能做到,我就处于获胜位置。如果您遵循相同的逻辑,您将意识到这种方法将唯一地识别头寸是赢还是输。因此,对于任何位置,我们都可以通过从 (1,1)
倒退到 (15,15)
来简单地构建答案网格来回答它是赢还是输。
现在如果板的数量超过一个,你会怎么做?您需要深入研究博弈论,尤其是 Grundy
数字以及它们与 Nim
游戏的关系。我建议您查看以下链接以获取更多信息:
https://en.wikipedia.org/wiki/Nim
https://en.wikipedia.org/wiki/Nimber
https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/
https://www.hackerrank.com/challenges/chessboard-game-again-1
上面的问题我试过下面的方式,但答案被评价为错误。(我不是在求解决方案,而是在问方法中的缺陷);
我的代码(请忽略c99错误)
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int numofmov = 0;
int issafe(int a,int b){
if(a>=0 && a<15 && b>=0 && b<15)
return 1;
return 0;
}
void move(int board[][15]){
for(int i=0;i<15;i++){
for(int j=0;j<15;j++){
if(board[i][j]>0){
board[i][j]--;
if(issafe(board,i-2,j+1)==1) {
numofmov++;
board[i-2][j+1]++;
}
if(issafe(board,i-2,j-1)==1) {
numofmov++;
board[i-2][j-1]++;
}
if(issafe(board,i+1,j-2)==1) {
numofmov++;
board[i+1][j-2]++;
}
if(issafe(board,i-1,j-2)==1) {
numofmov++;
board[i-1][j-2]++;
}
}
}
}
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int t;
scanf("%d",&t);
while(t--){
int k;
scanf("%d",&k);
int board[15][15];
for(int j=0;j<15;j++){
for(int h=0;h<15;h++){
board[j][h]=0;
}
}
for(int i=0;i<k;i++){
int x,y;
scanf("%d %d",&x,&y);
board[x-1][y-1]++;
}
int bro=0,mov=numofmov;
while(bro==0){
move(board);
if(numofmov==mov){
bro++;
printf("Second\n");
break;
}
mov = numofmov;
move(board);
if(numofmov==mov){
bro++;
printf("First\n");
break;
}
mov = numofmov;
}
}
return 0;
}
我的方法是继续使所有硬币的所有移动成为可能,直到我们到达无法移动的地步。但这在某些测试用例中给出了错误的答案。
您是在问这种方法有什么问题?
"My approach is to go on making all the moves possible for all the coins until we come to a point when no moves are possible. But this is giving wrong answers in some test cases."
我没有阅读您的代码,但我可以说主要问题是您的方法本身。您将此问题视为蛮力(制定所有可能的移动路径,看看谁赢了)。可能的移动数可以任意大,检查导致获胜的移动是无限慢的。实际上,它要么是动态规划,要么是更相关的博弈论问题。 这样想。起始位置是否唯一标识了这场比赛的获胜者?如果改变单个硬币的初始位置,获胜者是否也会改变?
解决此类问题的最佳方法是将其简化。 假设只有一个棋盘和一个硬币,位于 (x,y)
。现在请注意,每次将硬币从位置 (x,y)
移动到位置 (a,b)
后,以下内容为真 a+b<x+y
。因此,如果 (x,y)
是 (1,1),(1,2),(2,1),(2,2)
之一,则下棋的玩家已经输了。所以我的目标是确保我的对手从已经失去的位置开始行动,如果我能做到,我就处于获胜位置。如果您遵循相同的逻辑,您将意识到这种方法将唯一地识别头寸是赢还是输。因此,对于任何位置,我们都可以通过从 (1,1)
倒退到 (15,15)
来简单地构建答案网格来回答它是赢还是输。
现在如果板的数量超过一个,你会怎么做?您需要深入研究博弈论,尤其是 Grundy
数字以及它们与 Nim
游戏的关系。我建议您查看以下链接以获取更多信息:
https://en.wikipedia.org/wiki/Nim
https://en.wikipedia.org/wiki/Nimber
https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/