說明
由於迷宮的設計，老鼠走迷宮的入口至出口路徑可能不只一條，如何求出所有的路徑呢？解法
求所有路徑看起來複雜但其實更簡單，只要在老鼠走至出口時顯示經過的路徑，然後退回上一格重新選擇下一個位置繼續遞迴就可以了，比求出單一路徑還簡 單，我們的程式只要作一點修改就可以了。演算法
Procedure GO(maze[])
VISIT(maze, START_I, START_J, END_I, END_J)
Procedure VISIT(maze[], i, j, end_i, end_j)
IF maze[i][j] == 0
maze[i][j] = 1
IF maze[end_i][end_j] == 1
PRINT maze
ELSE
VISIT(maze, i, j + 1, end_i, end_j)
VISIT(maze, i + 1, j, end_i, end_j)
VISIT(maze, i, j - 1, end_i, end_j)
VISIT(maze, i - 1, j, end_i, end_j)
maze[i][j] = 0
實作：Toy C Java
Python Scala
Ruby JavaScript
Haskell Prolog
def pt(x, y) {
return new Object([['x', x], ['y', y]])
}
class Maze {
def init(raw) {
this.raw = raw
}
def get(x, y) {
return this.raw.get(x).get(y)
}
def set(x, y, v) {
this.raw.get(x).set(y, v)
}
def goalOrTry(st, ed) {
if this.get(ed.x, ed.y) {
this.print()
}
else {
this.visit(pt(st.x, st.y + 1), ed)
this.visit(pt(st.x + 1, st.y), ed)
this.visit(pt(st.x, st.y - 1), ed)
this.visit(pt(st.x - 1, st.y), ed)
}
}
def visit(st, ed) {
if not this.get(st.x, st.y) {
this.set(st.x, st.y, 1)
this.goalOrTry(st, ed)
this.set(st.x, st.y, 0)
}
}
def printSymbol(i, j) {
switch this.get(i, j) {
case 0
print(' ')
case 1
print('++')
case 2
print('██')
}
}
def printRow(i) {
(iterate(0, this.raw.get(i).length())
.forEach(j -> this.printSymbol(i, j)))
println()
}
def print() {
iterate(0, this.raw.length()).forEach(this.printRow)
}
}
(maze = new Maze([
[2, 2, 2, 2, 2, 2, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 0, 0, 2],
[2, 0, 2, 2, 0, 2, 2, 0, 2],
[2, 0, 2, 0, 0, 2, 0, 0, 2],
[2, 0, 2, 0, 2, 0, 2, 0, 2],
[2, 0, 0, 0, 0, 0, 2, 0, 2],
[2, 2, 0, 2, 2, 0, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 0, 0, 2],
[2, 2, 2, 2, 2, 2, 2, 2, 2]
]))
maze.visit(pt(1, 1), pt(7, 7))#include <stdio.h>
#include <stdlib.h>
#define SIZE 9
typedef struct {
int x;
int y;
} Point;
Point pt(int, int);
void visit(int[][SIZE], Point, Point, void (*)(int[][SIZE]));
void print(int[][SIZE]);
int main(void) {
int maze[SIZE][SIZE] = {{2, 2, 2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 2, 0, 2, 2, 0, 2},
{2, 0, 2, 0, 0, 2, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 0, 0, 0, 2, 0, 2},
{2, 2, 0, 2, 2, 0, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2, 2, 2}};
visit(maze, pt(1, 1), pt(7, 7), print);
return 0;
}
Point pt(int x, int y) {
Point p = {x, y};
return p;
}
void visit(int maze[][SIZE], Point start,
Point end, void (*take)(int[][SIZE])) {
if(!maze[start.x][start.y]) {
maze[start.x][start.y] = 1;
if(maze[end.x][end.y]) {
take(maze);
}
else {
visit(maze, pt(start.x, start.y + 1), end, take);
visit(maze, pt(start.x + 1, start.y), end, take);
visit(maze, pt(start.x, start.y - 1), end, take);
visit(maze, pt(start.x - 1, start.y), end, take);
}
maze[start.x][start.y] = 0;
}
}
void print(int maze[][SIZE]) {
int i, j;
for(i = 0; i < SIZE; i++) {
for(j = 0; j < SIZE; j++) switch(maze[i][j]) {
case 0 : printf(" "); break;
case 1 : printf("◇"); break;
case 2 : printf("█");
}
printf("\n");
}
}
import static java.lang.System.out;
class Point {
final int x;
final int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
interface Boss {
void take(int[][] maze);
}
public class Mouse {
public static void visit(int[][] maze, Point pt, Point end, Boss boss) {
if(isVisitable(maze, pt)) {
maze[pt.x][pt.y] = 1;
if(isEnd(maze, end)) {
boss.take(maze);
} else {
visit(maze, new Point(pt.x, pt.y + 1), end, boss);
visit(maze, new Point(pt.x + 1, pt.y), end, boss);
visit(maze, new Point(pt.x, pt.y - 1), end, boss);
visit(maze, new Point(pt.x - 1, pt.y), end, boss);
}
maze[pt.x][pt.y] = 0;
}
}
private static boolean isVisitable(int[][] maze, Point pt) {
return maze[pt.x][pt.y] == 0;
}
public static boolean isEnd(int[][] maze, Point end) {
return maze[end.x][end.y] == 1;
}
public static void main(String[] args) {
Mouse.visit(new int[][] {
{2, 2, 2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 2, 0, 2, 2, 0, 2},
{2, 0, 2, 0, 0, 2, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 0, 0, 0, 2, 0, 2},
{2, 2, 0, 2, 2, 0, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2, 2, 2}},
new Point(1, 1), new Point(7, 7),
// JDK8 Lambda
maze -> {
for(int[] row : maze) {
for(int block : row) switch(block) {
case 0: out.print(" "); break;
case 1: out.print("◇"); break;
case 2: out.print("█");
}
out.println();
}
}
);
}
}
class Mouse:
@staticmethod
def go(maze, start, end, take):
Mouse.visit(maze, start, end, [], take)
@staticmethod
def visit(maze, pt, end, route, take):
if Mouse.isVisitable(maze, pt, route):
route.append(pt)
if Mouse.isEnd(route, end):
take(maze, route)
else:
Mouse.visit(maze, (pt[0], pt[1] + 1), end, route, take)
Mouse.visit(maze, (pt[0] + 1, pt[1]), end, route, take)
Mouse.visit(maze, (pt[0], pt[1] - 1), end, route, take)
Mouse.visit(maze, (pt[0] - 1, pt[1]), end, route, take)
route.pop()
@staticmethod
def isVisitable(maze, pt, route):
return maze[pt[0]][pt[1]] == 0 and pt not in route
@staticmethod
def isEnd(route, end):
return end in route
def console(maze, route):
for i in range(len(maze)):
for j in range(len(maze[i])):
if (i, j) in route:
print("◇", end="")
else:
{
0 : lambda: print(" ", end=""),
2 : lambda: print("█",end="")
}[maze[i][j]]()
print()
Mouse.go([
[2, 2, 2, 2, 2, 2, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 0, 0, 2],
[2, 0, 2, 2, 0, 2, 2, 0, 2],
[2, 0, 2, 0, 0, 2, 0, 0, 2],
[2, 0, 2, 0, 2, 0, 2, 0, 2],
[2, 0, 0, 0, 0, 0, 2, 0, 2],
[2, 2, 0, 2, 2, 0, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 0, 0, 2],
[2, 2, 2, 2, 2, 2, 2, 2, 2]
], (1, 1), (7, 7), console)case class Point(x: Int, y: Int)
object Mouse {
def go(maze: List[List[Int]], start: Point, end: Point) = {
visit(maze, start, end, Nil)
}
def visit(maze: List[List[Int]], pt: Point,
end: Point, route: List[Point]): List[List[Point]] = {
if(isVisitable(maze, pt, route)) {
if(isEnd(pt, end)) {
(end::route)::Nil
} else {
visit(maze, Point(pt.x, pt.y + 1), end, pt::route) ++
visit(maze, Point(pt.x + 1, pt.y), end, pt::route) ++
visit(maze, Point(pt.x, pt.y - 1), end, pt::route) ++
visit(maze, Point(pt.x - 1, pt.y), end, pt::route)
}
} else {
Nil
}
}
def isVisitable(maze: List[List[Int]], pt: Point, route: List[Point]) = {
maze(pt.x)(pt.y) == 0 && !route.contains(pt)
}
def isEnd(pt: Point, end: Point) = {
pt == end
}
}
val maze = List(
List(2, 2, 2, 2, 2, 2, 2, 2, 2),
List(2, 0, 0, 0, 0, 0, 0, 0, 2),
List(2, 0, 2, 2, 0, 2, 2, 0, 2),
List(2, 0, 2, 0, 0, 2, 0, 0, 2),
List(2, 0, 2, 0, 2, 0, 2, 0, 2),
List(2, 0, 0, 0, 0, 0, 2, 0, 2),
List(2, 2, 0, 2, 2, 0, 2, 2, 2),
List(2, 0, 0, 0, 0, 0, 0, 0, 2),
List(2, 2, 2, 2, 2, 2, 2, 2, 2)
)
val allRoute = Mouse.go(maze, Point(1, 1), Point(7, 7))
allRoute.foreach( route =>
for(i <- 0 until maze.length) {
for(j <- 0 until maze(i).length) {
if(route.contains(Point(i, j))) {
print("◇")
} else {
maze(i)(j) match {
case 0 => print(" ")
case 2 => print("█")
}
}
}
println()
}
)
#encoding: Big5
class Mouse
def self.go(maze, start, goal)
visit(maze, start, goal, [], ->(m, r) { yield(m, r) })
end
def self.visit(maze, pt, goal, route, take)
if isVisitable(maze, pt, route)
route << pt
if isGoal(route, goal)
take.call(maze, route)
else
visit(maze, {x: pt[:x], y: pt[:y] + 1}, goal, route, take)
visit(maze, {x: pt[:x] + 1, y: pt[:y]}, goal, route, take)
visit(maze, {x: pt[:x], y: pt[:y] - 1}, goal, route, take)
visit(maze, {x: pt[:x] - 1, y: pt[:y]}, goal, route, take)
end
route.pop
end
end
def self.isVisitable(maze, pt, route)
maze[pt[:x]][pt[:y]] == 0 and not route.include? pt
end
def self.isGoal(route, goal)
route.include? goal
end
end
maze = [
[2, 2, 2, 2, 2, 2, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 0, 0, 2],
[2, 0, 2, 2, 0, 2, 2, 0, 2],
[2, 0, 2, 0, 0, 2, 0, 0, 2],
[2, 0, 2, 0, 2, 0, 2, 0, 2],
[2, 0, 0, 0, 0, 0, 2, 0, 2],
[2, 2, 0, 2, 2, 0, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 0, 0, 2],
[2, 2, 2, 2, 2, 2, 2, 2, 2]
]
Mouse.go(maze, {x: 1, y: 1}, {x: 7, y: 7}) do |maze, route|
0.upto(maze.size - 1) do |i|
0.upto(maze[i].size - 1) do |j|
if route.include?({x: i, y: j})
print "◇"
else
case maze[i][j]
when 0 then print " "
when 2 then print "█"
end
end
end
puts
end
end
var mouse = function() {
function isVisitable(maze, pt) {
return maze[pt.x][pt.y] === 0;
}
function isEnd(maze, end) {
return maze[end.x][end.y] === 1;
}
return function visit(maze, pt, end, take) {
if(isVisitable(maze, pt)) {
maze[pt.x][pt.y] = 1;
if(isEnd(maze, end)) {
take(maze);
}
else {
visit(maze, {x: pt.x, y: pt.y + 1}, end, take);
visit(maze, {x: pt.x + 1, y: pt.y}, end, take);
visit(maze, {x: pt.x, y: pt.y - 1}, end, take);
visit(maze, {x: pt.x - 1, y: pt.y}, end, take);
}
maze[pt.x][pt.y] = 0;
}
};
}();
mouse([[2, 2, 2, 2, 2, 2, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 0, 0, 2],
[2, 0, 2, 2, 0, 2, 2, 0, 2],
[2, 0, 2, 0, 0, 2, 0, 0, 2],
[2, 0, 2, 0, 2, 0, 2, 0, 2],
[2, 0, 0, 0, 0, 0, 2, 0, 2],
[2, 2, 0, 2, 2, 0, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 0, 0, 2],
[2, 2, 2, 2, 2, 2, 2, 2, 2]],
{x: 1, y: 1}, {x: 7, y: 7},
function(maze) {
var layout = '';
maze.forEach(function(row) {
row.forEach(function(block) {
switch(block) {
case 0: layout += ' '; break;
case 1: layout += '◇'; break;
case 2: layout += '█';
}
});
layout += '\n';
});
print(layout);
});
mouse maze start end = visit maze start end []
where visit maze pt end route =
if isVisitable maze pt route then
if isEnd pt end then (end:route):[]
else visit maze (fst pt, snd pt + 1) end (pt:route) ++
visit maze (fst pt + 1, snd pt) end (pt:route) ++
visit maze (fst pt, snd pt - 1) end (pt:route) ++
visit maze (fst pt - 1, snd pt) end (pt:route)
else []
isVisitable maze pt route =
maze !! fst pt !! snd pt == 0 && not (pt `elem` route)
isEnd pt end = pt == end
main = sequence[
sequence [putStrLn row | row <- toSymbol maze route]
| route <- mouse maze start end]
where maze = [[2, 2, 2, 2, 2, 2, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 0, 0, 2],
[2, 0, 2, 2, 0, 2, 2, 0, 2],
[2, 0, 2, 0, 0, 2, 0, 0, 2],
[2, 0, 2, 0, 2, 0, 2, 0, 2],
[2, 0, 0, 0, 0, 0, 2, 0, 2],
[2, 2, 0, 2, 2, 0, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 0, 0, 2],
[2, 2, 2, 2, 2, 2, 2, 2, 2]]
start = (1, 1)
end = (7, 7)
width = length maze
height = length \$ maze !! 0
toSymbol maze route = [[if (i, j) `elem` route then 'M'
else case (maze !! i !! j) of
0 -> ' '
2 -> 'X' | j <- [0..height - 1]
] | i <- [0..width - 1]]
contains(Pt, [Pt|_]).
contains(Pt, [_|T]) :- contains(Pt, T).
elem(Maze, [Px, Py], N) :-
nth0(Py, Maze, Row), nth0(Px, Row, N).
visitable(Maze, Route, Pt) :-
elem(Maze, Pt, 0), not(contains(Pt, Route)).
finish(Pt, Pt, Route, [Pt|Route]).
workaround(Maze, End, Route, Pt, Solution) :-
down(Maze, End, Route, Pt, Solution);
right(Maze, End, Route, Pt, Solution);
up(Maze, End, Route, Pt, Solution);
left(Maze, End, Route, Pt, Solution).
down(Maze, End, Route, [Px, Py], Solution) :-
Npy is Py + 1,
find(Maze, End, Route, [Px, Npy], Solution).
right(Maze, End, Route, [Px, Py], Solution) :-
Npx is Px + 1,
find(Maze, End, Route, [Npx, Py], Solution).
up(Maze, End, Route, [Px, Py], Solution) :-
Npy is Py - 1,
find(Maze, End, Route, [Px, Npy], Solution).
left(Maze, End, Route, [Px, Py], Solution) :-
Npx is Px - 1,
find(Maze, End, Route, [Npx, Py], Solution).
tryMore(Maze, End, Route, Pt, Solution) :-
workaround(Maze, End, [Pt|Route], Pt, Solution).
finish_or_tryMore(Maze, End, Route, Pt, Solution) :-
finish(End, Pt, Route, Solution); tryMore(Maze, End, Route, Pt, Solution).
find(Maze, End, Route, Pt, Solution) :-
visitable(Maze, Route, Pt), finish_or_tryMore(Maze, End, Route, Pt, Solution).
printMaze(_, X, Y, Solution) :- contains([X, Y], Solution), write("◇").
printMaze(0, _, _, _) :- write(" ").
printMaze(2, _, _, _) :- write("█").
printNext(T, Solution, X, Y) :- NX is X + 1, printRow(T, Solution, NX, Y).
printRow([], _, _, _) :- nl.
printRow([H|T], Solution, X, Y) :- printMaze(H, X, Y, Solution), printNext(T, Solution, X, Y).
printIt([Row|Rows], Solution, Y) :-
printRow(Row, Solution, 0, Y), NY is Y + 1, printIt(Rows, Solution, NY).
printIt([], _, _) :- nl.
printAll(_, []) :- nl, nl.
printAll(Maze, [H|T]) :- printIt(Maze, H, 0), printAll(Maze, T).
main(_) :-
Maze = [[2, 2, 2, 2, 2, 2, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 0, 0, 2],
[2, 0, 2, 2, 0, 2, 2, 0, 2],
[2, 0, 2, 0, 0, 2, 0, 0, 2],
[2, 0, 2, 0, 2, 0, 2, 0, 2],
[2, 0, 0, 0, 0, 0, 2, 0, 2],
[2, 2, 0, 2, 2, 0, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 0, 0, 2],
[2, 2, 2, 2, 2, 2, 2, 2, 2]],
findall(Solution, find(Maze,
[7, 7],
[],
[1, 1],
Solution
), Solutions),
printAll(Maze, Solutions).