调试/修复 BFS 算法

Question

我正在解决这个 BFS 作业问题，我相信我遵循的逻辑是正确的，但我陷入了一个无法查明的实现错误。我正在寻求调试此解决方案的帮助，而不是提出新的解决方案。

问题陈述：

一个孩子有两个远程控制的机器人，两个机器人都在 NxN 棋盘上，应该是放置在棋盘中的位置A和B上。

两个机器人同时受到遥控器的影响，同一个命令会影响两个机器人的状态。

遥控器一次只能使两个机器人顺时针或逆时针旋转90度，或者命令两个机器人向前移动。

示例： 最左边的图像显示了初始设置。向右的箭头是面向东的机器人，向上的箭头是面向北的机器人。位置A和B是机器人的命运。

中心图像显示了两个机器人向前移动一步的结果。

右图显示了使机器人逆时针旋转的结果。

孩子想要计算将机器人从初始位置带到目的地所需的最小移动次数。

如果命令机器人跑过墙壁，它将保持在同一位置。

如果命令两个机器人移动到同一位置，它们将保留在原来的位置。

图 2 显示了这种特殊情况。

两个机器人应该同时到达不同的命运。

输入： 输入由各种测试用例组成，第一行以输入矩阵（棋盘）大小为 N 的整数开头，其中 2<= N <=25。

下面的 N 行描述了棋盘，每行有 N 个字符。

一个“。”表示空位置。

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

input.txt 的正确输出：

8
3
-1

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

input2.txt 的“正确”（？）输出：

-1
-1
9
-1
46

我的解决方案：

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;

    }
}

问题： 1) 在第一个 input.txt 文件中，它找到 9 个动作来找到第一门课程的解决方案（当它们应该是 8 时）和 6 个动作来找到第二门课程的解决方案（当它们应该是是 3）尽管它正确地打印出最后一个（不可能的）课程配置的 -1 。

2) 在第二个 input.txt 文件中，教授说它应该为第一门课程打印 -1 和 -1，尽管我的程序为第二种情况找到了一个合理的解决方案，而为第一个课程找到了一个奇怪的解决方案首先（我认为更有经验的调试器可以提供帮助，我无法追踪第一种情况下移位命运输出的原因）。我的教授提出的输出正确吗？我的算法也陷入了应该打印 46 的情况。

Answer 1

有两个不小心的复制和粘贴问题导致代码无法工作，
1、顺时针转动部分：

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

            newR2Pos.orientation = 'O';

        }

这是错误的……应该是直接从上面的块复制粘贴的

        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中）和（A在Y中或B在X中）

虽然它是相同的（逻辑上不完全相同，但它在某种程度上适合你）如果 A 和 B 不能占据相同的位置），如果使用

(A in X and B in Y) 或 (A in Y and B in X)

会更清楚除了上面提到的致命错误之外，你的程序还有一个其他一些问题需要解决。看起来您是一名大学生学习计算机科学，请在编码之前阅读给定的源代码： TransistionState 类根本没有使用，但您创建了自己的 PositionsAndCounter，转动逻辑实现了两次，如果您没有重写转动代码，并使用给定的代码，你不会犯问题1……如果我是你的教授，我可能会让你在这方面失败。在敲击键盘之前先计划好你的解决方案，并确保你的代码清晰易读，如果你盯着源代码 5 分钟却无法弄清楚代码块的用途，可能是你没有正确构建它。

下面的清单是您的问题的示例解决方案：

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;
    }   
}

该程序在大约 10 秒内给出最终答案。

主要区别是我使用哈希表来存储测试状态以提高速度，因此哈希函数的质量会对速度产生影响。

推荐阅读：哈希表、DRY原理。