Anonymous user
Sokoban: Difference between revisions
→{{header|Java}}: added Java
(Undo revision 198283 by Bearophile (talk)) |
(→{{header|Java}}: added Java) |
||
Line 1,602:
ulULLulDDurrrddlULrruLLrrUruLLLulD</pre>
=={{header|Java}}==
Translation of [[Sokoban#C++|C++]] via [[Sokoban#D|D]]
{{works with|Java|7}}
<lang java>package sokoban;
import java.util.*;
public class Sokoban {
String destBoard, currBoard;
int playerX, playerY, nCols;
Sokoban(String[] board) {
nCols = board[0].length();
StringBuilder destBuf = new StringBuilder();
StringBuilder currBuf = new StringBuilder();
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < nCols; c++) {
char ch = board[r].charAt(c);
destBuf.append(ch != '$' && ch != '@' ? ch : ' ');
currBuf.append(ch != '.' ? ch : ' ');
if (ch == '@') {
this.playerX = c;
this.playerY = r;
}
}
}
destBoard = destBuf.toString();
currBoard = currBuf.toString();
}
String move(int x, int y, int dx, int dy, String trialBoard) {
int idx = (y + dy) * nCols + x + dx;
if (trialBoard.charAt(idx) != ' ')
return null;
char[] tmp = trialBoard.toCharArray();
tmp[y * nCols + x] = ' ';
tmp[idx] = '@';
return new String(tmp);
}
String push(int x, int y, int dx, int dy, String trialBoard) {
int idx = (y + 2 * dy) * nCols + x + 2 * dx;
if (trialBoard.charAt(idx) != ' ')
return null;
char[] tmp = trialBoard.toCharArray();
tmp[y * nCols + x] = ' '; // where the player was
tmp[(y + dy) * nCols + x + dx] = '@'; // where the player is now
tmp[idx] = '$'; // box has moved
return new String(tmp);
}
boolean isSolved(String trialBoard) {
for (int i = 0; i < trialBoard.length(); i++)
if ((destBoard.charAt(i) == '.') // goal
!= (trialBoard.charAt(i) == '$'))
return false;
return true;
}
String solve() {
class Board {
String cur, sol;
int x, y;
Board(String s1, String s2, int px, int py) {
cur = s1;
sol = s2;
x = px;
y = py;
}
}
char[][] dirLabels = {{'u', 'U'}, {'r', 'R'}, {'d', 'D'}, {'l', 'L'}};
int[][] dirs = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
Set<String> history = new HashSet<>();
LinkedList<Board> open = new LinkedList<>();
history.add(currBoard);
open.add(new Board(currBoard, "", playerX, playerY));
while (!open.isEmpty()) {
Board item = open.poll();
String cur = item.cur;
String sol = item.sol;
int x = item.x;
int y = item.y;
for (int i = 0; i < dirs.length; i++) {
String tmp = cur;
int dx = dirs[i][0];
int dy = dirs[i][1];
// are we standing next to a box?
if (tmp.charAt((y + dy) * nCols + x + dx) == '$') {
// let's see if we can push it
if ((tmp = push(x, y, dx, dy, tmp)) != null) {
// or did we already try this one?
if (!history.contains(tmp)) {
String newSol = sol + dirLabels[i][1];
if (isSolved(tmp))
return newSol;
open.add(new Board(tmp, newSol, x + dx, y + dy));
history.add(tmp);
}
}
// otherwise try change position
} else if ((tmp = move(x, y, dx, dy, tmp)) != null) {
if (!history.contains(tmp)) {
String newSol = sol + dirLabels[i][0];
open.add(new Board(tmp, newSol, x + dx, y + dy));
history.add(tmp);
}
}
}
}
return "No solution";
}
public static void main(String[] a) {
String level = "#######,# #,# #,#. # #,#. $$ #,"
+ "#.$$ #,#.# @#,#######";
System.out.println(new Sokoban(level.split(",")).solve());
}
}</lang>
<pre>ulULLulDDurrrddlULrruLLrrUruLLLulD</pre>
=={{header|OCaml}}==
|