2016-07-18 2 views
-1

https://www.hackerrank.com/challenges/chessboard-game-again-1체스 게임 ...하지만 다른 한

나는 다음과 같은 방법으로 위의 질문을 시도했지만 답변은 잘못된 것으로 평가된다. (I 해결책을 요구하고 있지 않다,하지만 난을 요구하고있다 접근의 결함);

내 코드합니다 (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; 
} 

내 접근 방식은 더 이동 할 수 없을 때 우리가 지점에 올 때까지 모든 동전을 위해 가능한 모든 움직임을 만들어 갈 것입니다. 그러나 이것은 일부 테스트 케이스에서 오답을주고있다.

+6

귀하의 질문은 링크에 전적으로 의존하고있다. 링크는 시간이 지남에 따라 깨질 수 있으므로 관련 코드와 따옴표를 질문에 포함하는 것이 좋습니다. – SurvivalMachine

+0

링크에 내 코드가 있습니다 ..... 작동하지 않습니까 ?? – yobro97

+0

네, 죄송합니다. 마크를 조금 빨리 벗어났습니다. 질문에 코드를 추가했습니다. 나는 또한'C++'태그를 빼 버렸다. 마치'c'처럼 보인다. 문제를 설명하면 문제가 개선 될 것입니다. –

답변

2

이 접근법에 어떤 문제가 있습니까?

"내 접근 방식은 우리가 더 이동이 가능하지 않는 점에 올 때까지 모든 동전을 위해 가능한 모든 움직임을 만들어 갈 것입니다. 그러나 이것은 는 몇 가지 테스트의 경우 잘못된 답을주고있다."

코드를 읽지는 않았지만 주요 문제는 접근 방식 자체라고 말할 수 있습니다. 당신은이 문제를 짐승 같은 힘으로 생각하고 있습니다 (가능한 모든 이동 경로를 만들고, 누가 승리하는지보십시오). 가능한 움직임의 수는 임의적으로 커질 수 있으며, 움직임이 무한히 느리게 진행되는 것을 확인합니다. 실제로 그것은 동적 프로그래밍이거나보다 관련있는 게임 이론 문제입니다. 이런 식으로 생각하십시오. 시작 위치가이 게임의 승자를 고유하게 식별합니까? 단일 동전의 초기 위치를 변경하면 승자도 변경됩니까?

이런 종류의 문제에 접근하는 가장 좋은 방법은이를 단순화하는 것입니다.(x,y)에 위치하는 단일 동전이있는 단일 보드 만 있다고 가정합니다. 이제 (x,y) 위치에서 (a,b) 위치로 동전을 옮기고 나면 다음 내용이 적용됩니다. a+b<x+y. 따라서 (x,y)(1,1),(1,2),(2,1),(2,2) 중 하나 인 경우 이동하는 플레이어는 이미 손실됩니다. 따라서 나의 목표는 상대방이 이미 잃어버린 위치에서 움직일 것이라는 것을 확실히하는 것입니다. 그리고 내가 그것을 할 수 있다면, 나는 승리 한 위치에 있습니다. u가 동일한 논리를 따르는 경우,이 접근법은 위치가 성공했는지 아니면 잃는지를 고유하게 식별한다는 것을 알게 될 것입니다. 따라서 어느 위치에서라도 (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/

관련 문제