Anonymous user
Sokoban: Difference between revisions
no edit summary
(→{{header|Ruby}}: refactering) |
No edit summary |
||
Line 742:
return 0;
}</lang>
=={{header|C sharp|C#}}==
<lang csharp>
public class SokobanSolver
{
private class Board
{
public string Cur { get; internal set; }
public string Sol { get; internal set; }
public int X { get; internal set; }
public int Y { get; internal set; }
public Board(string cur, string sol, int x, int y)
{
Cur = cur;
Sol = sol;
X = x;
Y = y;
}
}
private string destBoard, currBoard;
private int playerX, playerY, nCols;
SokobanSolver(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][c];
destBuf.Append(ch != '$' && ch != '@' ? ch : ' ');
currBuf.Append(ch != '.' ? ch : ' ');
if (ch == '@')
{
this.playerX = c;
this.playerY = r;
}
}
}
destBoard = destBuf.ToString();
currBoard = currBuf.ToString();
}
private string Move(int x, int y, int dx, int dy, string trialBoard)
{
int newPlayerPos = (y + dy) * nCols + x + dx;
if (trialBoard[newPlayerPos] != ' ')
return null;
char[] trial = trialBoard.ToCharArray();
trial[y * nCols + x] = ' ';
trial[newPlayerPos] = '@';
return new string(trial);
}
private string Push(int x, int y, int dx, int dy, string trialBoard)
{
int newBoxPos = (y + 2 * dy) * nCols + x + 2 * dx;
if (trialBoard[newBoxPos] != ' ')
return null;
char[] trial = trialBoard.ToCharArray();
trial[y * nCols + x] = ' ';
trial[(y + dy) * nCols + x + dx] = '@';
trial[newBoxPos] = '$';
return new string(trial);
}
private bool IsSolved(string trialBoard)
{
for (int i = 0; i < trialBoard.Length; i++)
if ((destBoard[i] == '.')
!= (trialBoard[i] == '$'))
return false;
return true;
}
private string Solve()
{
char[,] dirLabels = { { 'u', 'U' }, { 'r', 'R' }, { 'd', 'D' }, { 'l', 'L' } };
int[,] dirs = { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } };
ISet<string> history = new HashSet<string>();
LinkedList<Board> open = new LinkedList<Board>();
history.Add(currBoard);
open.AddLast(new Board(currBoard, string.Empty, playerX, playerY));
while (!open.Count.Equals(0))
{
Board item = open.First();
open.RemoveFirst();
string cur = item.Cur;
string sol = item.Sol;
int x = item.X;
int y = item.Y;
for (int i = 0; i < dirs.GetLength(0); i++)
{
string trial = cur;
int dx = dirs[i, 0];
int dy = dirs[i, 1];
// are we standing next to a box ?
if (trial[(y + dy) * nCols + x + dx] == '$')
{
// can we push it ?
if ((trial = Push(x, y, dx, dy, trial)) != null)
{
// or did we already try this one ?
if (!history.Contains(trial))
{
string newSol = sol + dirLabels[i, 1];
if (IsSolved(trial))
return newSol;
open.AddLast(new Board(trial, newSol, x + dx, y + dy));
history.Add(trial);
}
}
// otherwise try changing position
}
else if ((trial = Move(x, y, dx, dy, trial)) != null)
{
if (!history.Contains(trial))
{
string newSol = sol + dirLabels[i, 0];
open.AddLast(new Board(trial, newSol, x + dx, y + dy));
history.Add(trial);
}
}
}
}
return "No solution";
}
public static void Main(string[] a)
{
string level = "#######," +
"# #," +
"# #," +
"#. # #," +
"#. $$ #," +
"#.$$ #," +
"#.# @#," +
"#######";
System.Console.WriteLine("Level:\n");
foreach (string line in level.Split(','))
{
System.Console.WriteLine(line);
}
System.Console.WriteLine("\nSolution:\n");
System.Console.WriteLine(new SokobanSolver(level.Split(',')).Solve());
}
}
</lang>
=={{header|D}}==
| |||