Knight의 최소 이동량 디버그 Java

Question

기본적으로 기사가 0-63을 포함하는 8x8 격자의 특정 위치에 도달하는 데 필요한 최소의 이동량을 찾아야합니다.

나는 모든 테스트 케이스를 생각해 볼 수있는 모든 테스트 케이스를 교차 검사했으며 모든 테스트 케이스는 내가 찾고있는 것입니다. O (1) 솔루션을 모델로하지만 대신 나이트에 대한 제거 및 배치 알고리즘을 사용했습니다.

문제에 대해받은 테스트 케이스는 기밀이며 내가 놓친 것을 추측 할 수 밖에 없습니다. 코드를 확인하려고하면 다음과 같은 결과가 나타납니다.

테스트 1을 통과했습니다!
테스트 2가 실패했습니다.
테스트 3 통과했습니다!
테스트 4가 실패했습니다.
테스트 5가 실패했습니다.
테스트 6이 실패했습니다.
테스트 7이 실패했습니다.
테스트 8이 실패했습니다.
테스트 9가 실패했습니다.
테스트 10이 실패했습니다.

코드 :

public class Test { 

public static boolean found = false; 

public static void main (String[] args) { 

    int[][] arr = { // 0 1 2 3 4 5 6 7 
        { 0, 1, 2, 3, 4, 5, 6, 7}, // 0 
        { 8, 9, 10, 11, 12, 13, 14, 15}, // 1 
        {16, 17, 18, 19, 20, 21, 22, 23}, // 2 
        {24, 25, 26, 27, 28, 29, 30, 31}, // 3 
        {32, 33, 34, 35, 36, 37, 38, 39}, // 4 
        {40, 41, 42, 43, 44, 45, 46, 47}, // 5 
        {48, 49, 50, 51, 52, 53, 54, 55}, // 6 
        {56, 57, 58, 59, 60, 61, 62, 63}, // 7 
        }; 
    int src = 63; // Changed to parameters values later on in testing 
    int dest = 30; // Changed to parameters values later on in testing 

    int[] loc = pos(arr, src); 
    int[][] productMatrix; 
    int finalNumber = 0; 

    while(!found && arr[loc[0]][loc[1]] != dest) 
    { 
     productMatrix = createknights(arr, loc[0], loc[1], dest); 
     printMatrix(productMatrix); 
     System.out.println("--------------------"); 
     finalNumber++; 
    } 

    System.out.println(finalNumber); 


} 

public static int[][] createknights(int[][] arr, int r, int c, int goal) 
{ 
    arr[r][c] = -1; 
    int[][] knightLoc = getKnightLoc(arr); 

    for(int i = 0; i < knightLoc.length; i++) 
    { 
     int[][] possiblePositions = { 
             {knightLoc[i][0] - 2, knightLoc[i][1] - 1}, //Up Left 
             {knightLoc[i][0] - 2, knightLoc[i][1] + 1}, //Up Right 
             {knightLoc[i][0] + 2, knightLoc[i][1] - 1}, //Down Left 
             {knightLoc[i][0] + 2, knightLoc[i][1] + 1}, //Down Right 
             {knightLoc[i][0] - 1, knightLoc[i][1] - 2}, //Left Up 
             {knightLoc[i][0] + 1, knightLoc[i][1] - 2}, //Left Down 
             {knightLoc[i][0] - 1, knightLoc[i][1] + 2}, //Right Up 
             {knightLoc[i][0] + 1, knightLoc[i][1] + 2} //Right Down 
            }; 


     for(int[] row : possiblePositions) 
     { 
      if(checkLoc(arr, row[0], row[1])) 
      { 
       if(arr[row[0]][row[1]] == goal) 
       { 
        found = true; 
        break; 
       } 

       arr[row[0]][row[1]] = -1; 
      } 
     } 
    } 

    return arr; 
} 

public static int[][] getKnightLoc(int[][] arr) 
{ 
    int knightNum = getKnightNum(arr); 
    int[][] knightLocArray = new int[knightNum][2]; 

    for(int i = 0; i < arr.length; i ++) 
    { 
     for(int a = 0; a < arr[i].length; a++) 
     { 
      if(arr[i][a] == -1) 
      { 
       knightLocArray[(knightNum - 1)] = new int[]{i,a}; 
       knightNum--; 
      } 
     } 
    } 

    return knightLocArray; 
} 

public static int getKnightNum(int[][] arr) 
{ 
    int knightNum = 0; 

    for(int i = 0; i < arr.length; i ++) 
    { 
     for(int a = 0; a < arr[i].length; a++) 
     { 
      if(arr[i][a] == -1) 
      { 
       knightNum++; 
      } 
     } 
    }  

    return knightNum; 
} 

public static boolean checkLoc(int[][] arr, int r, int c) 
{ 
    if(r >= 0 && c >= 0 && r < arr.length && c < arr[r].length && arr[r][c] != -1) 
    { 
     return true; 
    } 

    return false; 
} 



public static int[] pos(int[][] arr, int src) 
{ 
    for(int i = 0; i < arr.length; i ++) 
    { 
     for(int a = 0; a < arr[i].length; a++) 
     { 
      if(arr[i][a] == src) 
      { 
       return new int[]{i , a}; 
      } 
     } 

    } 

    return null; 
} 

public static void printMatrix(int[][] arr) 
{ 
    for(int i = 0; i < arr.length; i ++) 
    { 
     for(int a = 0; a < arr[i].length; a++) 
     { 
      System.out.print(arr[i][a] + " "); 
     } 

     System.out.println(); 
    }  
} 
} 

모델 나는 내 답변을 확인 (1) O :

O(1) model

출력 예 (종료 값이 대답 : SRC = 63, 이명 령 = 30) :

0 1 2 3 4 5 6 7 
8 9 10 11 12 13 14 15 
16 17 18 19 20 21 22 23 
24 25 26 27 28 29 30 31 
32 33 34 35 36 37 38 39 
40 41 42 43 44 45 -1 47 
48 49 50 51 52 -1 54 55 
56 57 58 59 60 61 62 -1 
-------------------- 
0 1 2 3 4 5 6 7 
8 9 10 11 12 13 14 15 
16 17 18 19 20 21 22 23 
24 25 26 27 28 -1 30 -1 
32 33 34 35 -1 37 -1 39 
40 41 42 -1 44 45 -1 -1 
48 49 50 51 -1 -1 54 55 
56 57 58 -1 60 -1 62 -1 
-------------------- 
0 1 2 3 4 5 6 7 
8 9 10 11 -1 13 -1 15 
16 17 18 -1 20 -1 22 -1 
24 25 -1 27 -1 -1 30 -1 
32 -1 34 -1 -1 -1 -1 -1 
40 41 -1 -1 -1 45 -1 -1 
48 -1 50 -1 -1 -1 54 -1 
56 57 -1 -1 -1 -1 -1 -1 
-------------------- 
3 <----Answer 

알려주세요. ng. 감사!

편집 :

INT SRC & INT 이명 령은 하드 런타임에 코딩되지 않습니다. 값은 매개 변수 값으로 대체됩니다. 값은 테스트 목적으로 하드 코딩됩니다.

Answer 1

프로그램이 매번 3 번 인쇄됩니다. 이는 원본을 정사각형 63으로, 대상을 정사각형 30으로 하드 코드했기 때문입니다. 동시에 두 개의 테스트 사례에 대한 응답은 실제로 3입니다. 이는 합리적인 추측입니다. 그래서 당신은 그 두 가지를 통과하고 나머지는 실패합니다.

대신 할당을 통해 지정된 방식으로 입력 내용을 읽어야합니다.

Answer 2

이 코드 블록은 테스트 케이스가 하나의 연속 코드 섹션에서 테스트된다는 사실을 제외하고는 완벽한 솔루션입니다.

public static void main (String[] args) { 
    //Test Cases 
    System.out.println(answer(63,5)); 
    System.out.println(answer(19,4)); 
    System.out.println(answer(63,0)); 
} 

이 인쇄 것입니다 : 내가이 부분의 코드를 호출하는 별도의 방법을 허용하고 예를 들어

, 더 디버깅 후

5 
0 
0 

, 나는 원인이 있었는지 발견 앞에 오는 0은 코드 맨 위에있는 발견 된 변수를 무시합니다. 따라서 완전히 잘못된 대답으로 이어집니다.

이전 코드 :

while(!found && arr[loc[0]][loc[1]] != dest) 
{ 
    productMatrix = createknights(arr, loc[0], loc[1], dest); 
    printMatrix(productMatrix); 
    System.out.println("--------------------"); 
    finalNumber++; 
} 

System.out.println(finalNumber); 

새로운 코드 :

while(!found && arr[loc[0]][loc[1]] != dest) 
{ 
    productMatrix = createknights(arr, loc[0], loc[1], dest); 
    printMatrix(productMatrix); 
    System.out.println("--------------------"); 
    finalNumber++; 
} 

found = false; 

System.out.println(finalNumber); 

는 따라서 이제 정답을 중계.

감사합니다. Ole V.V. 해결책을 브레인 스토밍하기! 문제와 몇 가지 아이디어에서 약간의 시간이 필요하다고 생각합니다.