我正在解决这个 BFS 作业问题，我相信我遵循的逻辑是正确的，但我陷入了无法确定的实现错误。我正在寻求帮助调试此解决方案，而不是提出新的解决方案。
问题陈述：
一个孩子有两个他远程控制的机器人，两个机器人都在 NxN 棋盘上，应该放在棋盘的 A 和 B 位置。
两个机器人同时受到遥控器的影响，相同的命令会影响它们的两个状态。
遥控器只能使两个机器人同时顺时针或逆时针转动 90 度或命令两个机器人前进。
示例： 最左侧的图像显示初始设置。向右的箭头是朝东的机器人，朝上的箭头是朝北的机器人。位置 A 和 B 是机器人的命运。
中心图像显示了将两个机器人向前移动一步的结果。
右图显示了使机器人逆时针旋转的结果。
孩子希望计算将机器人从初始位置带到目的地所需的最少移动次数。
如果机器人被命令翻墙，它会留在原地。
如果两个机器人被命令移动到同一个位置，它们将留在原来的位置。
图 2 显示了这种特殊情况。
两个机器人应该同时到达不同的命运。
输入： 输入由各种测试用例组成，第一行以输入矩阵（棋盘）大小为 N 的整数开头，其中 2<= N <=25。
以下 N 行描述了棋盘格，每行有 N 个字符。
一个 '。' 表示空位。
N、E、S 或 O（西班牙语为 Oeste=West）表示机器人的原始位置和方向。
D 表示棋盘中机器人的命运，“*”表示障碍物。
输入以 N=0 的情况结束。
输入.txt
5
D....
N...S
.....
*...*
....D
5
.....
S..S.
.....
.....
D..D.
3
SN.
***
.DD
0
input.txt 的正确输出：
8
3
-1
输入2.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 的情况下。