BFS 알고리즘의 디버깅/수정

Question

나는이 BFS 숙제 문제를 해결하고 있으며, 내가 따르고있는 논리가 옳다고 생각하지만, 정확히 파악할 수없는 구현 오류에 빠져 들었다. 이 솔루션을 디버깅하는 데 도움이 필요하며 새로운 것을 제안하지 않습니다.

문제 설명 :

아이 모두 로봇에의 nxn 바둑판 있고 바둑판의 위치 A 및 B에 배치해야 그가 원격 제어 두 로봇을 갖는다.

두 로봇은 동시에 리모컨의 영향을받습니다. 동일한 명령이 두 상태 모두에 영향을줍니다.

리모콘은 한 번에 두 로봇을 시계 방향 또는 반 시계 방향으로 90 도씩 만 돌리거나 두 로봇이 앞으로 이동하도록 명령 할 수 있습니다.

예 : 가장 왼쪽의 이미지는 초기 설정을 보여줍니다. 오른쪽을 가리키는 화살표는 동쪽을 향한 로봇이고 위쪽을 향하고있는 arraw는 북쪽을 향한 로봇입니다. 위치 A와 B는 로봇 운명입니다.

가운데 이미지는 두 로봇을 한 단계 앞으로 이동 한 결과를 보여줍니다.

오른쪽 이미지는 로봇을 반 시계 방향으로 회전시킨 결과를 보여줍니다.

아이가 자신의 운명을 자신의 초기 위치에서 로봇을하는 데 필요한 움직임의 최소 수를 계산하기 원하신다.

로봇이 벽을 뛰어 넘는 명령을 받으면 로봇은 같은 지점에 남습니다.

두 로봇은 같은 지점으로 이동하라는 명령을 받으면 원래 위치에 남아 있습니다.

그림 2는이 특별한 경우를 보여줍니다.

두 로봇은 동시에 다른 운명에 도착한다.

는

입력 : 입력 다양한 테스트 케이스로 구성되어, 상기 제 2 라인은 < < = N = 25의 inputMatrix (바둑판)의 크기가 N 인 정수 시작한다.

다음 N 줄은 바둑판을 묘사하고 각각 N 자입니다.

A '.' 빈 위치를 나타냅니다.

N, E, S 또는 O (Oeste = West의 경우 스페인어)는 로봇의 원래 위치와 방향을 나타냅니다.

D는 바둑판에서 로봇의 운명을 나타내고 '*'는 장애물을 나타냅니다.

N = 0 인 경우 입력이 완료됩니다.

입력.input.txt를위한

5 
D.... 
N...S 
..... 
*...* 
....D 
5 
..... 
S..S. 
..... 
..... 
D..D. 
3 
SN. 
*** 
.DD 
0 

올바른 출력 TXT :

8 
3 
-1 

input2.txt :

-1 
-1 
9 
-1 
46 

(?)에 대한 input2.txt

5 
..... 
..D.S 
.D... 
..... 
..N.. 
6 
...... 
..S... 
...... 
.ED... 
...... 
.D.... 
11 
....E...... 
....D...... 
........... 
..S...D.... 
........... 
........... 
........... 
........... 
........... 
........... 
........... 
13 
............. 
............. 
............. 
............. 
.....N....... 
............. 
.........D... 
..D.......... 
............. 
...E......... 
............. 
............. 
............. 
25 
...*.......*.*........... 
........*..D...*.**....*. 
*..*.*.........*..*..*..D 
...*.**.*........*...*... 
......**..*..***.***...** 
.............*........... 
....*...***.....*.**..... 
......**.......**.*.*...* 
.........*..*...*.*...... 
....**.*.*....**.*.*.*.*. 
.......*............**... 
..........*.*.....*...... 
...........**....*.**.... 
.....E.*.*..........**.*. 
.........*.*.*.*..*..*... 
*........**...*.......... 
................***..*... 
........*....*....*...*.. 
......*...*.*...*.....**. 
...*..........*.**....... 
.**............*.*..*.*.. 
........*........*...*... 
*......*..........*...... 
*...*......N*......*..*.* 
. .....*..*.*..*...*...... 
0 

"올바른"출력

내 솔루션 :

import java.io.BufferedReader; 
import java.io.File; 
import java.io.FileReader; 
import java.io.IOException; 
import java.util.ArrayList; 
import java.util.LinkedList; 
import java.util.Queue; 




class Position { 

    int i; 
    int j; 
    char orientation; 

     Position() { 

    } 


    void setIJ(int i, int j){ 
     this.i=i; 
     this.j=j; 
    } 

    void setOrientation(char c){ 

     orientation = c; 
    } 

    public boolean equals(Object o){ 

     if(o instanceof Position){ 

      Position p = (Position)o; 
      if((p.i==this.i)&&(p.j==this.j)&&(p.orientation==this.orientation)) 
      { 
       return true; 
      } 
       else return false; 
      } 

      return false; 
    } 

} //end class Position 


class TransitionState { 

    Position positionA; 
    Position positionB; 

    int counter; 

    public boolean equals (Object o){ 

     if (o instanceof TransitionState){ 

      TransitionState transitionState= (TransitionState)o; 

      if ((this.positionA.equals(transitionState.positionA)) 
        &&(this.positionB.equals(transitionState.positionB))) 
      { 
       return true; 
      } 
     } 
    return false; 

    } 

} 


public class Robots { 

static Position moveForward(Position oldPosition, int matrixSize, char orientation, char [][] inputMatrix){ 

    // add possible new Position 
    Position newPosition= new Position(); 

    //first return oldPosition in border positions in which the robot shouldn't move 

    if ((orientation=='O')&&(oldPosition.j==0)) 
      return oldPosition; 

    if ((orientation=='E')&&(oldPosition.j==(matrixSize-1))) 
      return oldPosition; 

    if ((orientation=='N')&&(oldPosition.i==0)) 
      return oldPosition; 

    if ((orientation=='S')&&(oldPosition.i==(matrixSize-1))) 
      return oldPosition; 


    if ((orientation=='O')) 
     newPosition.setIJ(oldPosition.i, oldPosition.j-1); 
    if ((orientation=='E')) 
     newPosition.setIJ(oldPosition.i, oldPosition.j+1); 
    if ((orientation=='S')) 
     newPosition.setIJ(oldPosition.i-1, oldPosition.j); 
    if ((orientation=='N')) 
     newPosition.setIJ(oldPosition.i+1, oldPosition.j); 


    //return oldPosition for positions in which the robot is blocked by * 
    if (inputMatrix[newPosition.i][newPosition.j]=='*'){ 
     return oldPosition; 
    } 

    return newPosition; // if it got here, all ok 

} 


static char turnCounter (char orientation){ 

    if(orientation=='N') 
     return 'O'; 
    if(orientation=='O') 
     return 'S'; 
    if (orientation=='S') 
     return 'E'; 
    else 
     return 'N'; 

} 

static char turnClock(char orientation){ 

     if(orientation=='N') 
     return 'E'; 
    if(orientation=='E') 
     return 'S'; 
     if (orientation=='S') 
     return 'O'; 
    else 
     return 'N'; 

} 

static Position[] robotInitialPositions(char [][]inputMatrix){ 

    Position [] helperArray = new Position[2]; 

    int aux=0; 

    for (int i=0; i<(inputMatrix[0].length); i++) 
     for (int j=0; j<(inputMatrix[0].length); j++) 
     { 
      if((inputMatrix[i][j]=='N')||(inputMatrix[i][j]=='S')||(inputMatrix[i][j]=='O')||(inputMatrix[i][j]=='E')) 
      { 
        helperArray[aux]= new Position(); 
        helperArray[aux].setIJ(i, j); 
        if (inputMatrix[i][j]=='N'){helperArray[aux].orientation='N'; } 
        if (inputMatrix[i][j]=='S'){helperArray[aux].orientation='S'; } 
        if (inputMatrix[i][j]=='E'){helperArray[aux].orientation='E'; } 
        if (inputMatrix[i][j]=='O'){helperArray[aux].orientation='O'; } 
        aux= aux+1; 
      } 

     } 

    return helperArray; 

} 


static Position[] getDestinies(char [][]inputMatrix){ 

    Position [] helperArray = new Position[2]; 

    int aux=0; 

    for (int i=0; i<(inputMatrix[0].length); i++) 
     for (int j=0; j<(inputMatrix[0].length); j++) 
     { 
      if((inputMatrix[i][j]=='D')) 
      { 
        helperArray[aux]= new Position(); 
        helperArray[aux].i=i; helperArray[aux].j=j; 
        helperArray[aux].orientation='D'; 
        aux=aux+1; 

      } 

     } 

    return helperArray; 

} 



static boolean [][]getUnvisitedMatrix(int matrixLength){ 


    boolean[][] unvisitedMatrix = new boolean [matrixLength][matrixLength]; 

    for (int i=0; i<matrixLength;i++) 
     for (int j=0; j<matrixLength; j++) 
      unvisitedMatrix[i][j]=false; 

    return unvisitedMatrix; 

} 





static Position[]getNewRobotPositions (Position oldR1Pos,Position oldR2Pos, String movement, char [][]inputMatrix){ 

    Position[]newPositions = new Position[2]; 

    Position newR1Pos = new Position(); 
     Position newR2Pos = new Position(); 

    if(movement.equals("counter")){ 

     if (oldR1Pos.orientation=='N'){ 

      newR1Pos.orientation='O'; 

     } 

     if (oldR1Pos.orientation=='S'){ 

      newR1Pos.orientation='E'; 

     } 

     if (oldR1Pos.orientation=='E'){ 

      newR1Pos.orientation='N'; 

     } 

     if (oldR1Pos.orientation=='O'){ 

      newR1Pos.orientation='S'; 
     } 


     if (oldR2Pos.orientation=='N'){ 

      newR2Pos.orientation='O'; 
     } 

     if (oldR2Pos.orientation=='S'){ 

      newR2Pos.orientation='E'; 

     } 

     if (oldR2Pos.orientation=='E'){ 

      newR2Pos.orientation='N'; 

     } 

     if (oldR2Pos.orientation=='O'){ 

      newR2Pos.orientation='S'; 

     } 

     newR1Pos.i=oldR1Pos.i; 
     newR1Pos.j=oldR1Pos.j; 

     newR2Pos.i=oldR2Pos.i; 
     newR2Pos.j=oldR2Pos.j; 

     newPositions[0]=newR1Pos; 
     newPositions[1]=newR2Pos; 

//  System.out.println("MOVED COUNTERCLOCKWISE"); 
//  System.out.println("previous Robot 1 position was "+oldR1Pos.i + ","+oldR1Pos.j + " orientation was " + oldR1Pos.orientation + 
//  " new Robot 1 position is " + newR1Pos.i + "," + newR1Pos.j+ " orientation is "+newR1Pos.orientation); 
// 
//  System.out.println("previous Robot 2 position was "+oldR2Pos.i + ","+oldR2Pos.j + " orientation was " + oldR2Pos.orientation + 
//  " new Robot 2 position is " + newR2Pos.i + "," + newR2Pos.j+ " orientation is "+newR2Pos.orientation); 

     return newPositions; 


    } 

    if(movement.equals("clock")){ 

     newR1Pos.i = oldR1Pos.i; 
     newR1Pos.j = oldR1Pos.j; 

     newR2Pos.i = oldR2Pos.i; 
     newR2Pos.j = oldR2Pos.j; 


     if (oldR1Pos.orientation=='N'){ 

      newR1Pos.orientation= 'E'; 
     } 

     if (oldR1Pos.orientation=='S'){ 

      newR1Pos.orientation= 'O'; 
     } 

     if (oldR1Pos.orientation=='E'){ 

      newR1Pos.orientation= 'S'; 
     } 

     if (oldR1Pos.orientation=='O'){ 

      newR1Pos.orientation= 'N'; 

     } 



     if (oldR2Pos.orientation=='N'){ 

      newR2Pos.orientation= 'E'; 
     } 

     if (oldR2Pos.orientation=='S'){ 

      newR2Pos.orientation= 'O'; 

     } 

     if (oldR2Pos.orientation=='E'){ 

      newR2Pos.orientation= 'O'; 

     } 

     if (oldR2Pos.orientation=='O'){ 

      newR2Pos.orientation= 'N'; 

     } 
//  System.out.println("MOVED CLOCKWISE"); 
//  System.out.println("previous Robot 1 position was "+oldR1Pos.i + ","+oldR1Pos.j + " orientation was " + oldR1Pos.orientation + 
//  " new Robot 1 position is " + newR1Pos.i + "," + newR1Pos.j+ " orientation is "+newR1Pos.orientation); 
//
//  System.out.println("previous Robot 2 position was "+oldR2Pos.i + ","+oldR2Pos.j + " orientation was " + oldR2Pos.orientation + 
//  " new Robot 2 position is " + newR2Pos.i + "," + newR2Pos.j+ " orientation is "+newR2Pos.orientation); 


     newPositions[0]=newR1Pos; 
     newPositions[1]=newR2Pos; 

     return newPositions; 

    } 

    if(movement.equals("forward")){ 

     //default case, if conditions not satisfied 
     newR1Pos.i=oldR1Pos.i; 
     newR1Pos.j=oldR1Pos.j; 
      newR1Pos.orientation = oldR1Pos.orientation; 

     newR2Pos.i=oldR2Pos.i; 
     newR2Pos.j=oldR2Pos.j; 
     newR2Pos.orientation = oldR2Pos.orientation; 


     if(oldR1Pos.orientation=='N'){ 

      if(oldR1Pos.i-1>=0){ //doesn't exceed the upper border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR1Pos.i-1][oldR1Pos.j]!='*'){ 
         newR1Pos.i=oldR1Pos.i-1; 
         newR1Pos.j=oldR1Pos.j; 
         newR1Pos.orientation = oldR1Pos.orientation; 
       } 

      } 

     } 

     if(oldR1Pos.orientation=='S'){ 

      if(oldR1Pos.i+1<inputMatrix.length){ //doesn't exceed the lower border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR1Pos.i+1][oldR1Pos.j]!='*'){ 
         newR1Pos.i=oldR1Pos.i+1; 
         newR1Pos.j=oldR1Pos.j; 
         newR1Pos.orientation = oldR1Pos.orientation; 

       } 
      } 
     } 

     if(oldR1Pos.orientation=='E'){ 

      if(oldR1Pos.j+1<inputMatrix.length){ //doesn't exceed the right border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR1Pos.i][oldR1Pos.j+1]!='*'){ 
         newR1Pos.i=oldR1Pos.i; 
         newR1Pos.j=oldR1Pos.j+1; 
         newR1Pos.orientation = oldR1Pos.orientation; 
       } 
      } 

     } 

     if(oldR1Pos.orientation=='O'){ 

      if(oldR1Pos.j-1>=0){ //doesn't exceed the left border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR1Pos.i][oldR1Pos.j-1]!='*'){ 
         newR1Pos.i=oldR1Pos.i; 
         newR1Pos.j=oldR1Pos.j-1; 
         newR1Pos.orientation = oldR1Pos.orientation; 
       } 

      } 

     } 

     //same for robot 2 

     if(oldR2Pos.orientation=='N'){ 

      if(oldR2Pos.i-1>=0){ //doesn't exceed the upper border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR2Pos.i-1][oldR2Pos.j]!='*'){ 
         newR2Pos.i=oldR2Pos.i-1; 
         newR2Pos.j=oldR2Pos.j; 
         newR2Pos.orientation=oldR2Pos.orientation; 
       } 

      } 

     } 

     if(oldR2Pos.orientation=='S'){ 

      if(oldR2Pos.i+1<inputMatrix.length){ //doesn't exceed the lower border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR2Pos.i+1][oldR2Pos.j]!='*'){ 
         newR2Pos.i=oldR2Pos.i+1; 
         newR2Pos.j=oldR2Pos.j; 
         newR2Pos.orientation=oldR2Pos.orientation; 
       } 
      } 
     } 

     if(oldR2Pos.orientation=='E'){ 

      if(oldR2Pos.j+1<inputMatrix.length){ //doesn't exceed the right border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR2Pos.i][oldR2Pos.j+1]!='*'){ 
         newR2Pos.i=oldR2Pos.i; 
         newR2Pos.j=oldR2Pos.j+1; 
         newR2Pos.orientation=oldR2Pos.orientation; 
       } 
      } 

     } 

     if(oldR2Pos.orientation=='O'){ 

      if(oldR2Pos.j-1>=0){ //doesn't exceed the left border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR2Pos.i][oldR2Pos.j-1]!='*'){ 
         newR2Pos.i=oldR2Pos.i; 
         newR2Pos.j=oldR2Pos.j-1; 
         newR2Pos.orientation=oldR2Pos.orientation; 
       } 

      } 

     } 


     //if robots collide in new positions, revert to their original positions 
     if ((newR1Pos.i==newR2Pos.i) && (newR1Pos.j==newR2Pos.j)){ 

      //revert robot 1 position 
      newR1Pos.i=oldR1Pos.i; 
      newR1Pos.j=oldR1Pos.j; 
      newR1Pos.orientation = oldR1Pos.orientation; 

      //revert robot 2 position 
      newR2Pos.i=oldR2Pos.i; 
      newR2Pos.j=oldR2Pos.j; 
      newR2Pos.orientation = oldR2Pos.orientation; 
     } 

     newPositions[0] = newR1Pos; 
     newPositions[1] = newR2Pos; 

//  System.out.println("MOVED FORWARD"); 
//   System.out.println("previous Robot 1 position was "+oldR1Pos.i + ","+oldR1Pos.j + " orientation was " + oldR1Pos.orientation + 
//  " new Robot 1 position is " + newR1Pos.i + "," + newR1Pos.j+ " orientation is "+newR1Pos.orientation); 
// 
//  System.out.println("previous Robot 2 position was "+oldR2Pos.i + ","+oldR2Pos.j + " orientation was " + oldR2Pos.orientation + 
//  " new Robot 2 position is " + newR2Pos.i + "," + newR2Pos.j+ " orientation is "+newR2Pos.orientation); 

    } //end movement.equals("forward") 


    return newPositions; 

} 


//1 procedure BFS(Graph,source): 
//2  create a queue Q 
//3  enqueue source onto Q 
//4  mark source 
//5  while Q is not empty: 
//6   dequeue an item from Q into v 
//7   for each edge e incident on v in Graph: 
//8    let w be the other end of e 
//9    if w is not marked: 
//10     mark w 
//11     enqueue w onto Q 



static void BFS (char [][] inputMatrix){ 

    ArrayList<TransitionState> transitionStatesArray = new ArrayList<TransitionState>(); 

    int moveCounter=0; //turns and forward movements add here 

    int tempMoveCounterRobot1=0; int tempMoveCounterRobot2=0; 
    int maxMoveCounter=0; 

    PositionsAndCounter positionsAndCounter= new PositionsAndCounter(); 

    Queue <PositionsAndCounter>queue = new LinkedList<PositionsAndCounter>(); 

    Position robotInitial[] = robotInitialPositions(inputMatrix); //get source 
    positionsAndCounter.positionPair=robotInitial; //used to encapsulate the positions with a counter to output 
    positionsAndCounter.counter=0;//first initialize to 0 

    Position destinies[] = getDestinies(inputMatrix); //get destinies 


    TransitionState firstTransitionState = new TransitionState(); 
    firstTransitionState.positionA=robotInitial[0]; 
    firstTransitionState.positionB=robotInitial[1]; 

    transitionStatesArray.add(firstTransitionState); 

    //mark transition used , if the transition is new, it should be queued 

    queue.add(positionsAndCounter); 

    String [] movement = {"forward", "counter", "clock"}; 
    //possible movements inside inputMatrix 


    outer: while (!queue.isEmpty()){ //while queue is not empty 

     PositionsAndCounter v= queue.poll(); //dequeue an item from Q into V 

     for(int k = 0; k<3; k++){ //for each edge e incident on v in Graph: 

      Position[] newRobotPositions = getNewRobotPositions(v.positionPair[0], v.positionPair[1], movement[k], inputMatrix); 

      TransitionState newTransitionState = new TransitionState(); 
      newTransitionState.positionA=newRobotPositions[0]; 
      newTransitionState.positionB=newRobotPositions[1]; 

      if(!transitionStatesArray.contains(newTransitionState)){ //if the transition state is new add and enqueue new robot positions 

       transitionStatesArray.add(newTransitionState); 

        //if transition is new then queue 
       PositionsAndCounter newPositionsAndCounter = new PositionsAndCounter(); 
       newPositionsAndCounter.positionPair=newRobotPositions; 
       newPositionsAndCounter.counter = v.counter +1; 


        queue.add(newPositionsAndCounter); 


      } 


      inputMatrix[v.positionPair[0].i][v.positionPair[1].j]='.'; 
      inputMatrix[v.positionPair[1].i][v.positionPair[1].j]='.'; 

      //inputMatrix[v[0].i][v[0].j]='.'; // mark old position of robot 1 with . 
      //inputMatrix[v[1].i][v[1].j]='.'; // mark old position of robot 2 with . 

      //update new robot positions 
      inputMatrix[newRobotPositions[0].i][newRobotPositions[0].j]= newRobotPositions[0].orientation; 
      inputMatrix[newRobotPositions[1].i][newRobotPositions[1].j]= newRobotPositions[1].orientation; 


      //check if solution has been found 
        if 
        (
        ((destinies[0].i==newRobotPositions[0].i)&&(destinies[0].j==newRobotPositions[0].j) //robot in 0 arrived to destiny 
        || (destinies[1].i==newRobotPositions[0].i)&&(destinies[1].j==newRobotPositions[0].j))// in 0 or 1 
         &&                          //and 
        ((destinies[0].i==newRobotPositions[1].i)&&(destinies[0].j==newRobotPositions[1].j) //robot in 1 arrived to destiny 
        || (destinies[1].i==newRobotPositions[0].i)&&(destinies[1].j==newRobotPositions[0].j))//in 0 or 1 

        ) //end if 
        { 

         System.out.println("robots arrived at destinies"); 
         System.out.println("robot 1, starting at " + robotInitial[0].i + "," + robotInitial[0].j 
           + " is in " + newRobotPositions[0].i + ","+ newRobotPositions[0].j); 
         System.out.println("robot 2, starting at " + robotInitial[1].i + "," + robotInitial[1].j 
           + " is in " + newRobotPositions[1].i + ","+ newRobotPositions[1].j); 

        System.out.println("movements: " + (v.counter)); 

        return; 
        //break outer; 

        } 


       } 

      } 

      System.out.println("robots can never arrive at their destinies"); 
      System.out.println(-1); 


    } 


static void printInputMatrix(char [][] inputMatrix){ 


    for (int i=0; i<inputMatrix[0].length;i++) 
     for(int j=0; j<inputMatrix[0].length;j++) 
     { 

      System.out.print(" "+inputMatrix[i][j]+" "); 
      if(j==inputMatrix[0].length-1){System.out.println("");} 

     } 


} 





    public static void main(String[] args) throws IOException { 

//  System.out.println("Test transition checker"); 
//  Position p1 = new Position(); 
//  p1.i=1; 
//  p1.j=1; 
//  p1.orientation='N'; 
//  Position p2 = new Position(); 
//  p2.i=1; 
//  p2.j=2; 
//  p2.orientation='N'; 
//  Position p3 = new Position(); 
//  p3.i=1; 
//  p3.j=1; 
//  p3.orientation='N'; 
//  Position p4 = new Position(); 
//  p4.i=1; 
//  p4.j=1; 
//  p4.orientation='N'; 
// 
//  TransitionState transitionChecker1 = new TransitionState(); 
//  transitionChecker1.positionA=p1; 
//  transitionChecker1.positionB=p2; 
// 
//  TransitionState transitionChecker2 = new TransitionState(); 
//  transitionChecker2.positionA=p1; 
//  transitionChecker2.positionB=p2; 
// 
// 
//  ArrayList<TransitionState> arrayTransitions = new ArrayList<TransitionState>(); 
//  arrayTransitions.add(transitionChecker1); 
//  System.out.println("Test contains? " + arrayTransitions.contains(transitionChecker2)); 




     BufferedReader br = new BufferedReader(new FileReader(new File("input.txt"))); 

     char [][] inputMatrix; 

     String line; 
     char [] lineAsCharArray; 
     int matrixSize; 

     while(true){ 

      line = br.readLine(); 
      matrixSize=Integer.parseInt(line); 

      inputMatrix = new char [matrixSize][matrixSize]; 

      if (matrixSize==0){ // end outer looping 
       break; 
      } 

      else { //begin inner looping 

       for (int i=0; i<matrixSize; i++){ 

        line = br.readLine(); 
        inputMatrix[i] =line.toCharArray(); 

       } 

       //matrix loaded 

       BFS(inputMatrix); 

      } 


     } 

    } 

} 

class PositionsAndCounter { 

    Position[] positionPair; 
    int counter; 

    PositionsAndCounter() { 
     positionPair = new Position[2]; 
     counter=0; 

    } 
} 

문제 : 첫 번째 input.txt를 파일에 1), 그것은의 해결책을 찾기 위해 그들이 8 있어야 첫 번째 코스의 솔루션()와 (6)을 찾기 위해 9 개 움직임을 찾습니다 두 번째 코스 (3 일 때)는 마지막 (불가능한) 코스 구성에 -1을 올바르게 출력합니다.

2) 두 번째 input.txt 파일에서 교수님은 첫 번째 코스의 경우 -1과 -1을 인쇄해야한다고 말하지만 내 프로그램은 두 번째 케이스의 경우 가능한 솔루션을 찾고 첫 번째 케이스의 경우 기괴한 솔루션을 찾습니다 (이것은 내가 경험있는 디버거가 도움이 될 수 있다고 생각하는 곳이다. 나는 첫 번째 경우에 실향 된 운명 결과에 대한 이유를 추적하지 못하고있다). 내 교수가 제안한 결과물이 맞습니까? 내 알고리즘 또한 46이 인쇄되어야하는 경우에 붙어 있습니다.

 if (oldR2Pos.orientation == 'E') { 

      newR2Pos.orientation = 'O'; 

     } 

이 잘못은 ... 그것은 직접 복사해야하며에서 붙여 넣기한다 :

Answer 1

2 부주의 복사 및 붙여 넣기 문제는 코드가 시계 방향으로 회전 부분에, 1을 작동하지 않는 원인은 위의 블록

 if (oldR2Pos.orientation == 'E') { 

      newR2Pos.orientation = 'S'; 
     } 

아직 보지 못했습니다.

또 다른 문제는 최종 조건을 테스트 블록

 //check if solution has been found 
      if 
      (
      ((destinies[0].i==newRobotPositions[0].i)&&(destinies[0].j==newRobotPositions[0].j) //robot in 0 arrived to destiny 
      || (destinies[1].i==newRobotPositions[0].i)&&(destinies[1].j==newRobotPositions[0].j))// in 0 or 1 
       &&                          //and 
      ((destinies[0].i==newRobotPositions[1].i)&&(destinies[0].j==newRobotPositions[1].j) //robot in 1 arrived to destiny 
      || **(destinies[1].i==newRobotPositions[0].i)&&(destinies[1].j==newRobotPositions[0].j)**)//in 0 or 1 

      ) //end if 

마지막 부분에서 실제로 (코드를 강조) 그것은 분명히 사본입니다

(destinies[1].i==newRobotPositions[1].i)&&(destinies[1].j==newRobotPositions[1].j) 

하고 붙여 넣기하지만 오류를 변경하는 것을 잊지합니다. 논리는 이해하기 조금 어렵지만, 작동

(A X 또는 B Y에서의)과 (X에서 Y의 A 또는 B)가 논리적으로하지 정확히 (동일하지만

A와 B가 같은 위치를 차지할 수없는 경우에도 마찬가지 임)

(X는 A, Y는 B) 또는 (X는 Y와 B)

위에서 언급 한 치명적인 오류 이외에도 프로그램에 몇 가지 다른 문제가 있습니다. 컴퓨터 과학을하는 대학생처럼 보입니다. 주어진 소스 코드를 읽어보십시오. befo 다시 코딩 : TransistionState 클래스는 전혀 사용되지 않지만 자신의 PositionsAndCounter를 만들었고, 선회 코드를 다시 작성하지 않고 주어진 알고리즘을 사용하지 않으면 선회 논리가 두 번 구현됩니다. 문제는 1이 아닙니다.내가 너의 교수라면 나는 너에게 실패 할 수도있어. 키보드를 누르기 전에 솔루션을 계획하고 5 분 동안 소스 코드를 보았을 때 코드 블록이 무엇인지 파악할 수 없다면 코드가 명확하고 영어로 읽을 수 있는지 확인하십시오. 올바르게 구조화하십시오. 이 프로그램은 약 10 초 최종 답변을 뱉어

import java.awt.Point; 
import java.io.BufferedReader; 
import java.io.FileReader; 
import java.io.IOException; 
import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.LinkedList; 
import java.util.List; 
import java.util.Map; 


public class DualRobot { 

    public enum Orientation{ 
     E(1, 0), S(0, 1), O(-1, 0), N(0, -1); 

     public final int dx, dy; 
     private Orientation(int dx, int dy){ 
      this.dx = dx; 
      this.dy = dy; 
     } 

     public Orientation left(){ 
      return Orientation.values()[(this.ordinal() + 3) % 4]; 
     } 

     public Orientation right(){ 
      return Orientation.values()[(this.ordinal() + 1) % 4]; 
     } 

     public static Orientation valueOf(char c){ 
      for(Orientation o : Orientation.values()){ 
       if(o.toString().equalsIgnoreCase("" + c)) return o; 
      } 
      return null; 
     } 

    } 

    public enum Action {FORWARD, COUNTER_CLOCKWISE, CLOCKWISE}; // F: forward, L: Counter clockwise, R: clockwise 

    private static class Robot{ 
     Point position; 
     Orientation orientation; 

     public Robot(Robot r){ 
      this.position = new Point(r.position); 
      this.orientation = r.orientation; 
     } 
     public Robot(int x, int y, Orientation orientation){ 
      this.position = new Point(x, y); 
      this.orientation = orientation; 
     } 

     public void move(Action action, char[][] map){ 
      switch (action) { 
      case FORWARD: 
       Point nextPosition = new Point(position); 
       nextPosition.translate(orientation.dx, orientation.dy); 
       if(isValidPosition(nextPosition, map)) position = nextPosition; 
       break; 
      case COUNTER_CLOCKWISE: 
       this.orientation = this.orientation.left(); 
       break; 
      case CLOCKWISE: 
       this.orientation = this.orientation.right(); 
       break; 
      } 
     } 

     @Override 
     public boolean equals(Object obj) { 
      if (obj instanceof Robot) { 
       Robot r = (Robot) obj; 
       return r.position.equals(this.position) && r.orientation == this.orientation; 
      } 
      return super.equals(obj); 
     } 

     @Override 
     public int hashCode() { 
      return orientation.ordinal() + position.x * 10 + position.y * 1000; 
     } 

     private boolean isValidPosition(Point p, char[][] map){ 
      return p.x >= 0 && p.x < map[0].length 
       && p.y >= 0 && p.y < map.length 
       && map[p.y][p.x] != '*'; 
     } 
    } 

    private static class State{ 
     private Robot a, b; 
     private int counter; 

     public State(Robot a, Robot b, int counter) { 
      this.a = new Robot(a); 
      this.b = new Robot(b); 
      this.counter = counter; 
     } 

     public List<State> nextStates(char[][] map){ 
      List<State> states = new ArrayList<State>(); 
      for(Action action : Action.values()){ 
       State s = new State(this.a, this.b, this.counter + 1); 
       s.a.move(action, map); 
       s.b.move(action, map); 
       if(!s.a.position.equals(s.b.position)){ // Test for collision 
        states.add(s); 
       } 
      } 
      return states; 
     } 

     @Override 
     public boolean equals(Object obj) { 
      if (obj instanceof State) { 
       State state = (State) obj; // Consider the state to be the same if the 2 robots are at identical location and orientation 
       return (this.a.equals(state.a) && this.b.equals(state.b)) 
        || (this.a.equals(state.b) && this.b.equals(state.a)); 
      } 
      return super.equals(obj); 
     } 

     @Override 
     public int hashCode() { 
      // The quality of this hashCode can affect the program's speed 
      // Multiply is transitive, so if you swap a and b, the hashcode is the same 
      return a.hashCode() * b.hashCode(); 
     } 

    } 

    public static void main(String[] args) throws IOException { 
     BufferedReader input = new BufferedReader(new FileReader("input.txt")); 
     int size; 

     while((size = Integer.parseInt(input.readLine())) > 0){ 
      // Load the data; 
      char[][] map = new char[size][size]; 
      for (int i = 0; i < size; i++) { 
       map[i] = input.readLine().toCharArray(); 
      } 

      // Construct initial state 
      List<Robot> robots = new ArrayList<Robot>(); 
      List<Point> destinations = new ArrayList<Point>(); 
      for(int i = 0; i < size; i ++){ 
       for(int j = 0; j < size; j ++){ 
        Orientation orientation = Orientation.valueOf(map[i][j]); 
        if(orientation != null){ 
         robots.add(new Robot(j, i, orientation)); 
        }else if(map[i][j] == 'D'){ 
         destinations.add(new Point(j, i)); 
        } 
       } 
      } 

      System.out.println(BFSSearch(map, new State(robots.get(0), robots.get(1), 0), destinations)); 

     } 

    } 

    private static int BFSSearch(char[][] map, State initialState, List<Point> destinations) throws IOException{ 
     List<State> queue = new LinkedList<State>(); // Array list is slightly more efficient 
     queue.add(initialState); // Initial state 
     Map<State, Boolean> testedStates = new HashMap<State, Boolean>(); 
     while(queue.size() > 0){ 
      State currentState = queue.remove(0); 
      if(testedStates.containsKey(currentState)) continue; 

      // Testing for end condition 
      if((currentState.a.position.equals(destinations.get(0)) && currentState.b.position.equals(destinations.get(1))) 
      || (currentState.a.position.equals(destinations.get(1)) && currentState.b.position.equals(destinations.get(0)))){ 
       return currentState.counter; 
      } 
      testedStates.put(currentState, true); 
      queue.addAll(currentState.nextStates(map)); 
     } 
     return -1; 
    } 
} 

:

아래의 목록은 귀하의 질문에 대한 예제 솔루션입니다.

가장 큰 차이점은 테스트 된 상태를 저장하기 위해 해시 테이블을 사용하여 속도를 향상 시켜서 해시 함수의 품질이 속도에 영향을 미친다는 점입니다.

추천 정보 : 해시 테이블, DRY 원칙.