私はこのBFSの宿題の問題を解決しています。私がフォローしているロジックは正しいと思いますが、特定できない実装エラーで立ち往生しています。新しいソリューションを提案するのではなく、このソリューションをデバッグするためのヘルプを探しています。
問題文：
子供には、リモートで制御する2台のロボットがあります。どちらのロボットもNxNチェッカーボード上にあり、チェッカーボードの位置AとBに配置する必要があります。
両方のロボットが同時にリモートコントローラーの影響を受け、同じコマンドが両方の状態に影響します。
リモコンは、両方のロボットを一度に時計回りまたは反時計回りに90度回転させるか、両方のロボットに前進させることしかできません。
例： 左端の画像は初期設定を示しています。右向きの矢印は東向きのロボットで、上向きの矢印は北向きのロボットです。位置AとBはロボットの運命です。
中央の画像は、両方のロボットを1歩前進させた結果を示しています。
右の画像は、ロボットを反時計回りに回転させた結果を示しています。
子供は、ロボットを初期位置から目的地まで移動させるために必要な最小動作数を計算したいと考えています。
ロボットが壁を越えて走るように命じられた場合、ロボットは同じ場所に留まります。
同じ場所に移動するように指示された場合、両方のロボットは元の場所に留まります。
図2は、この特殊なケースを示しています。
両方のロボットが同時に異なる運命に到着する必要があります。
入力： 入力はさまざまなテストケースで構成され、最初の行はinputMatrix（チェッカーボード）のサイズ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である必要がある場合）と、2番目のコースの解決策を見つけるための6つの動き（3である必要がある場合）が見つかります。最後の（不可能な）コース構成に対して-1を正しく出力します。
2） 2番目のinput.txtファイルで、教授は最初のコースに-1と-1を出力する必要があると言っていますが、私のプログラムは2番目のケースにはもっともらしい解決策を見つけ、最初のケースには奇妙な解決策を見つけます（これは私が思うところです）より経験豊富なデバッガーが役立つ可能性があります。最初のケースで運命の出力が置き換えられた理由を追跡するのに迷っています）。私の教授が提案した成果は正しいですか？私のアルゴリズムも、46を印刷する必要がある場合に行き詰まっています。