Anonymous user
Maze solving: Difference between revisions
no edit summary
No edit summary |
|||
Line 3,957:
| | o - o - o - o | | |
+---+---+---+---+---+---+---+---+---+---+---+
</pre>
=={{header|Picat}}==
<lang Picat>main =>
Maze0 = ["+---+---+---+---+---+---+---+---+",
"| | | | |",
"+ + + +---+ + +---+ +",
"| | | | | |",
"+---+---+ + +---+---+ + +",
"| | | | |",
"+---+ + + +---+---+---+ +",
"| | | | |",
"+ + + +---+---+---+ + +",
"| | | | | |",
"+ + + +---+ +---+---+ +",
"| | | | | |",
"+ +---+---+ +---+---+---+ +",
"| | | |",
"+ +---+ +---+ + +---+ +",
"| | | |",
"+---+---+---+---+---+---+---+---+"],
MaxR = len(Maze0) div 2,
MaxC = len(Maze0[1]) div 4,
Maze = new_array(MaxR,MaxC),
foreach (R in 1..MaxR, C in 1..MaxC)
Maze[R,C] = 0
end,
fill_maze(Maze0,Maze,1),
solve_maze(Maze,(1,1),(MaxR,MaxC),Cost,Plan),
OutputMaze = new_array(MaxR,MaxC),
foreach ((R,C) in Plan)
OutputMaze[R,C] = '*'
end,
output_maze(Maze0,OutputMaze,1).
fill_maze([Line1,Line2|Maze0],Maze,R) =>
fill_maze_cols(Line1,Maze,R,1),
fill_maze_cols(Line2,Maze,R,1),
fill_maze(Maze0,Maze,R+1).
fill_maze(_,_,_) => true.
fill_maze_cols(['+',' ',' ',' '|Line],Maze,R,C) =>
Maze[R,C] := Maze[R,C] \/ 4, % up
Maze[R-1,C] := Maze[R-1,C] \/ 8, % down
fill_maze_cols(Line,Maze,R,C+1).
fill_maze_cols([' ',' ',' ',' '|Line],Maze,R,C) =>
Maze[R,C] := Maze[R,C] \/ 1, % left
Maze[R,C-1] := Maze[R,C-1] \/ 2, % right
fill_maze_cols(Line,Maze,R,C+1).
fill_maze_cols([_,_,_,_|Line],Maze,R,C) =>
fill_maze_cols(Line,Maze,R,C+1).
fill_maze_cols(_,_,_,_) => true.
table (+,+,+,min,-)
solve_maze(_Maze,FPos,FPos,Cost,Plan) =>
Cost = 0,
Plan = [FPos].
solve_maze(Maze,Pos@(R,C),FPos,Cost,Plan) ?=>
Maze[R,C] /\ 1 == 1, % left
solve_maze(Maze,(R,C-1),FPos,Cost1,Plan1),
Plan = [Pos|Plan1],
Cost = Cost1+1.
solve_maze(Maze,Pos@(R,C),FPos,Cost,Plan) ?=>
Maze[R,C] /\ 2 == 2, % right
solve_maze(Maze,(R,C+1),FPos,Cost1,Plan1),
Plan = [Pos|Plan1],
Cost = Cost1+1.
solve_maze(Maze,Pos@(R,C),FPos,Cost,Plan) ?=>
Maze[R,C] /\ 4 == 4, % up
solve_maze(Maze,(R-1,C),FPos,Cost1,Plan1),
Plan = [Pos|Plan1],
Cost = Cost1+1.
solve_maze(Maze,Pos@(R,C),FPos,Cost,Plan) ?=>
Maze[R,C] /\ 8 == 8, % down
solve_maze(Maze,(R+1,C),FPos,Cost1,Plan1),
Plan = [Pos|Plan1],
Cost = Cost1+1.
output_maze([Line1,Line2|Maze0],Maze,R) =>
output_maze_cols(Line1,Maze,R,1),
output_maze_cols(Line2,Maze,R,1),
output_maze(Maze0,Maze,R+1).
output_maze([Line],_,_) => println(Line).
output_maze_cols([' ',' ',' ',' '|Line],Maze,R,C) =>
if Maze[R,C] == '*' then
print(" * ")
else
print(" ")
end,
output_maze_cols(Line,Maze,R,C+1).
output_maze_cols(['|',' ',' ',' '|Line],Maze,R,C) =>
if Maze[R,C] == '*' then
print("| * ")
else
print("| ")
end,
output_maze_cols(Line,Maze,R,C+1).
output_maze_cols(['+',' ',' ',' '|Line],Maze,R,C) =>
if Maze[R,C] == '*' && Maze[R-1,C] == '*' then
print("+ * ")
else
print("+ ")
end,
output_maze_cols(Line,Maze,R,C+1).
output_maze_cols([C1,C2,C3,C4|Line],Maze,R,C) =>
printf("%c%c%c%c",C1,C3,C3,C4),
output_maze_cols(Line,Maze,R,C+1).
output_maze_cols(Line,_,_,_) => println(Line).
</lang>
{{out}}
<pre>
+---+---+---+---+---+---+---+---+
| * | * * | | |
+ * + * + * +---+ + +---+ +
| * * | * | | | |
+---+---+ * + +---+---+ + +
| | * | | |
+---+ + * + +---+---+---+ +
| | * | | |
+ + + * +---+---+---+ + +
| | | * | | |
+ + + * +---+ +---+---+ +
| | | * * | | |
+ +---+---+ * +---+---+---+ +
| | * * | * * * |
+ +---+ +---+ * + * +---+ * +
| | * * | * |
+---+---+---+---+---+---+---+---+
</pre>
| |||