Привет!Вот уже несколько дней пытаюсь понять решение игры “RushHour”. Условия этой игры такие: красная машинка "аа" должна за короткое время дойти до финиша: координат {2,4} и {2,5}. Тоесть машинки которые преграждают ей путь к финишной позиции, надо за короткое время передвинуть так чтоб они не мешали. Эта програмка сделана из 4 классов: RushHourFrame, Board, State и StateQueue. Не могу понять функцию Solve() в классе Board. Может ли мне кто-то прокоментировать эту функцию шаг-за шагом. Буду вам очень признательна за помощь!!!  В чём заключается решение(отгадка) этой програмки???  Добавлено @ 14:25 код игры: | Код |
import java.util.*;
/**
*
*
*/
public class Board
{
private State beginState;
private char[] carNames = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q'};
private int numCars;
private State endState;
private State[] sollution;
private int sollutionLength = 0;
/**
* Constructor.
* Makes a new board with the String given to it. It also calculates how many cars there are.
*/
public Board(String s)
{
beginState = new State(s);
for(int i=0; i<s.length(); i++)
{
if(s.charAt(i) != '.')
{
for(int j=0; j<carNames.length; j++)
{
if(carNames[j] == s.charAt(i) && ( (j+1) > numCars))
{
numCars = j+1;
}
}
}
}
}
/**
* This function returns the values of the beginstate.
*/
public String getValue()
{
return beginState.toString();
}
/**
* This function returns the values of the endstate.
*/
public String getEndState()
{
return endState.toString();
}
/**
* This function returns the size of the sollution.
* (how many steps it takes to solve it)
*/
public int getSollutionLength()
{
return sollutionLength;
}
/**
* This returns the values of a given step of the sollution.
*/
public String getSollution(int i)
{
if(sollution[i].toString() != null) return sollution[i].toString();
else return "null";
}
/**
* This Functions solves the game (beginstate)
*/
public void Solve()
{
State temp = null;
StateQueue q = new StateQueue();
Hashtable visited = new Hashtable();
q.Add(beginState);
visited.put(beginState.toString(), 1);
boolean solved = false;
while(!solved)
{
temp = null;
temp = q.getFirst();
solved = temp.isSolved();
for(int i=0; i<numCars; i++)
{
State temp2 = temp.moveBackward(carNames[i]);
if(temp2 != null) temp2.addParent(temp);
if(temp2 != null)
{
if(!visited.containsKey(temp2.toString()))
{
q.Add(temp2);
visited.put(temp2.toString(),1);
}
}
temp2 = null;
temp2 = temp.moveForward(carNames[i]);
if(temp2 != null) temp2.addParent(temp);
if(temp2 != null)
{
if(!visited.containsKey(temp2.toString()))
{
q.Add(temp2);
visited.put(temp2.toString(),1);
}
}
temp2 = null;
}
}
endState = temp;
sollution = new State[500];
while(temp != null)
{
sollution[sollutionLength] = temp;
sollutionLength++;
temp = temp.getParent();
}
}
}
|
| Код |
public class State
{
private char[][] parking = new char[6][6];
private State parent = null;
/**
* Constructor.
* It sets all the values given with the string in the array.
*/
public State(String s)
{
if(s.length() == 36)
{
int k = 0;
for(int i=0; i<6; i++)
{
for(int j=0; j<6; j++)
{
this.parking[i][j] = s.charAt(k);
k++;
}
}
}
}
/**
* This function adds a parent to the State, so you can see where this state came from.
*/
public void addParent(State p)
{
parent = p;
}
/**
* This function returns the parent.
*/
public State getParent()
{
return parent;
}
/**
* This function returns the values of the state in a String.
*/
public String toString()
{
String s = "";
for(int i=0; i<6; i++)
{
for(int j=0; j<6; j++)
{
s+= parking[i][j];
}
}
return s;
}
/**
* Sets the value of a certain place on the ParkingPlace.
*/
public void setValue(int i, int j, char c)
{
parking[i][j] = c;
}
/**
* Moves a car backward(or upward) one place.
*/
public State moveBackward(char car)
{
State returnstate = new State(this.toString());
int k=0;
int i=0;
int j=0;
String s = "";
for(int i2=0;i2<6;i2++)
{
for(int j2=0;j2<6;j2++)
{
if(this.parking[i2][j2] == car)
{
if(k==0)
{
i = i2;
j = j2;
}
k++;
s+= i2 + "" + j2;
}
}
}
boolean horizontal = this.isHorizontal(s);
if(horizontal)
{
if(j-1 >= 0)
{
if(this.parking[i][j-1] == '.')
{
returnstate.setValue(i,j-1,car);
returnstate.setValue(i,j+(k-1), '.');
return returnstate;
}
}
}
else
{
if(i-1 >= 0)
{
if(this.parking[i-1][j] == '.')
{
returnstate.setValue(i-1,j,car);
returnstate.setValue(i+(k-1),j, '.');
return returnstate;
}
}
}
returnstate = null;
return returnstate;
}
/**
* Moves a car forward(or downward) one place.
*/
public State moveForward(char car)
{
State returnstate = new State(this.toString());
int k=0;
int i=0;
int j=0;
String s = "";
for(int i2=0;i2<6;i2++)
{
for(int j2=0;j2<6;j2++)
{
if(this.parking[i2][j2] == car)
{
if(k==0)
{
i = i2;
j = j2;
}
k++;
s+= i2 + "" + j2;
}
}
}
boolean horizontal = this.isHorizontal(s);
if(horizontal)
{
if(j+k < 6)
{
if(this.parking[i][j+k] == '.')
{
returnstate.setValue(i,j+k,car);
returnstate.setValue(i,j, '.');
return returnstate;
}
}
}
else
{
if(i+k < 6)
{
if(this.parking[i+k][j] == '.')
{
returnstate.setValue(i+k,j,car);
returnstate.setValue(i,j, '.');
return returnstate;
}
}
}
returnstate = null;
return returnstate;
}
/**
* Checks if a car is horizontal or vertical.
*/
public boolean isHorizontal(String s)
{
if(s.charAt(0) == s.charAt(2))
return true;
else
return false;
}
/**
* Checks if the puzzle is solved.
*/
public boolean isSolved()
{
return (parking[2][4] == 'a') && (parking[2][5] == 'a'); // finaljnaja pozicija
}
}
|
| Код |
import java.util.*;
/**
*
*
*/
public class StateQueue
{
Vector states = new Vector();
/**
* Adds a state on the back of the line.
*/
public void Add(State s)
{
states.add(s);
}
/**
* Returns the first State in line.
*/
public State getFirst()
{
State s = (State)states.elementAt(0);
states.remove(0);
return s;
}
}
|
|
алгоритм RushHour, алгоритм игры RushHour 
Загрузка ...
