說明
老鼠走迷宮是遞迴求解的基本題型，我們在二維陣列中使用2表示迷宮牆壁，使用1來表示老鼠的行走路徑，試以程式求出由入口至出口的路徑。
解法
老鼠的走法有上、左、下、右四個方向，在每前進一格之後就選一個方向前進，無法前進時退回選擇下一個可前進方向，如此在陣列中依序測試四個方向，直到
走到出口為止，這是遞迴的基本題，請直接看程式應就可以理解。
演算法
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] == 0
IF !(VISIT(maze, i, j + 1, end_i, end_j) OR
VISIT(maze, i + 1, j, end_i, end_j) OR
VISIT(maze, i, j - 1, end_i, end_j) OR
VISIT(maze, i - 1, j, end_i, end_j))
maze[i][j] = 0
RETURN maze[end_i][end_j] == 1
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 visit(st, ed) {
if not this.get(st.x, st.y) {
this.set(st.x, st.y, 1)
if not this.get(ed.x, ed.y) and not this.tryOneOut(st, ed) {
this.set(st.x, st.y, 0)
}
}
return this.get(ed.x, ed.y)
}
def tryOneOut(st, ed) {
(return this.visit(pt(st.x, st.y + 1), ed) or
this.visit(pt(st.x + 1, st.y), ed) or
this.visit(pt(st.x, st.y - 1), ed) or
this.visit(pt(st.x - 1, st.y), ed))
}
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, 0, 0, 0, 0, 0, 2],
[2, 0, 2, 0, 2, 0, 2],
[2, 0, 0, 2, 0, 2, 2],
[2, 2, 0, 2, 0, 2, 2],
[2, 0, 0, 0, 0, 0, 2],
[2, 2, 2, 2, 2, 2, 2]
]))
if not maze.visit(pt(1, 1), pt(5, 5)) {
println('沒有找到出口！')
}
maze.print()
#include <stdio.h>
#include <stdlib.h>
#define SIZE 7
typedef struct {
int x;
int y;
} Point;
Point pt(int, int);
int visit(int[][SIZE], Point, Point);
void print(int[][SIZE]);
int main(void) {
int maze[SIZE][SIZE] = {{2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 2, 0, 2, 2},
{2, 2, 0, 2, 0, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2}};
if(!visit(maze, pt(1, 1), pt(5, 5))) {
printf("\n沒有找到出口！\n");
}
print(maze);
return 0;
}
Point pt(int x, int y) {
Point p = {x, y};
return p;
}
int visit(int maze[][SIZE], Point start, Point end) {
if(!maze[start.x][start.y]) {
maze[start.x][start.y] = 1;
if(!maze[end.x][end.y] &&
!(visit(maze, pt(start.x, start.y + 1), end) ||
visit(maze, pt(start.x + 1, start.y), end) ||
visit(maze, pt(start.x, start.y - 1), end) ||
visit(maze, pt(start.x - 1, start.y), end))) {
maze[start.x][start.y] = 0;
}
}
return maze[end.x][end.y];
}
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;
}
}
public class Mouse {
public static int[][] go(int[][] maze, Point start, Point end) {
visit(maze, start, end);
return maze;
}
public static boolean visit(int[][] maze, Point pt, Point end) {
if(isVisitable(maze, pt)) {
maze[pt.x][pt.y] = 1;
if(!isEnd(maze, end) && !tryOneOut(maze, pt, end)) {
maze[pt.x][pt.y] = 0;
}
}
return isEnd(maze, end);
}
public 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 boolean tryOneOut(int[][] maze, Point pt, Point end) {
return visit(maze, new Point(pt.x, pt.y + 1), end) ||
visit(maze, new Point(pt.x + 1, pt.y), end) ||
visit(maze, new Point(pt.x, pt.y - 1), end) ||
visit(maze, new Point(pt.x - 1, pt.y), end);
}
public static void main(String[] args) {
int[][] maze = new int[][]{{2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 2, 0, 2, 2},
{2, 2, 0, 2, 0, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2}};
for(int[] row : Mouse.go(maze, new Point(1, 1), new Point(5, 5))) {
for(int block : row) switch(block) {
case 0: out.print(" "); break;
case 1: out.print("◇"); break;
case 2: out.print("█");
}
out.println();
}
out.println(Mouse.isEnd(maze, new Point(5, 5))
? "找到出口" : "沒有找到出口！");
}
}
class Mouse:
@staticmethod
def go(maze, start, end):
route = []
Mouse.visit(maze, start, end, route)
return route
@staticmethod
def visit(maze, pt, end, route):
if Mouse.isVisitable(maze, pt, route):
route.append(pt)
if not Mouse.isEnd(route, end) and \
not Mouse.tryOneOut(maze, pt, end, route):
route.pop()
return Mouse.isEnd(route, end)
@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
@staticmethod
def tryOneOut(maze, pt, end, route):
return Mouse.visit(maze, (pt[0], pt[1] + 1), end, route) or \
Mouse.visit(maze, (pt[0] + 1, pt[1]), end, route) or \
Mouse.visit(maze, (pt[0], pt[1] - 1), end, route) or \
Mouse.visit(maze, (pt[0] - 1, pt[1]), end, route)
maze = [[2, 2, 2, 2, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 2],
[2, 0, 2, 0, 2, 0, 2],
[2, 0, 0, 2, 0, 2, 2],
[2, 2, 0, 2, 0, 2, 2],
[2, 0, 0, 0, 0, 0, 2],
[2, 2, 2, 2, 2, 2, 2]]
for pt in Mouse.go(maze, (1, 1), (5, 5)):
maze[pt[0]][pt[1]] = 1
if maze[5][5] == 0:
print("找不到出口")
for row in maze:
for block in row:
{
0 : lambda: print(" ", end=""),
1 : lambda: print("◇", end=""),
2 : lambda: print("█",end=""),
}[block]()
print()
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[Point] = {
if(isVisitable(maze, pt, route)) {
if(isEnd(pt, end)) end::route
else tryOneOut(maze, pt, 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
def tryOneOut(maze: List[List[Int]], pt: Point,
end: Point, route: List[Point]) = {
or(visit(maze, Point(pt.x, pt.y + 1), end, route)) {
or(visit(maze, Point(pt.x + 1, pt.y), end, route)) {
or(visit(maze, Point(pt.x, pt.y - 1), end, route)) {
visit(maze, Point(pt.x - 1, pt.y), end, route)
}
}
}
}
def or(expr1: => List[Point])(expr2: => List[Point]) = {
val route = expr1
if(route == Nil) expr2 else route
}
}
val maze = List(
List(2, 2, 2, 2, 2, 2, 2),
List(2, 0, 0, 0, 0, 0, 2),
List(2, 0, 2, 0, 2, 0, 2),
List(2, 0, 0, 2, 0, 2, 2),
List(2, 2, 0, 2, 0, 2, 2),
List(2, 0, 0, 0, 0, 0, 2),
List(2, 2, 2, 2, 2, 2, 2)
)
val route = Mouse.go(maze, Point(1, 1), Point(5, 5))
if(!route.contains(Point(5, 5))) {
println("找不到出口")
}
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)
route = []
visit(maze, start, goal, route)
route
end
def self.visit(maze, pt, goal, route)
if isVisitable(maze, pt, route)
route << pt
if not isGoal(route, goal) and
not tryOneOut(maze, pt, goal, route)
route.pop
end
end
isGoal(route, goal)
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
def self.tryOneOut(maze, pt, goal, route)
visit(maze, {x: pt[:x], y: pt[:y] + 1}, goal, route) or
visit(maze, {x: pt[:x] + 1, y: pt[:y]}, goal, route) or
visit(maze, {x: pt[:x], y: pt[:y] - 1}, goal, route) or
visit(maze, {x: pt[:x] - 1, y: pt[:y]}, goal, route)
end
end
maze = [
[2, 2, 2, 2, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 2],
[2, 0, 2, 0, 2, 0, 2],
[2, 0, 0, 2, 0, 2, 2],
[2, 2, 0, 2, 0, 2, 2],
[2, 0, 0, 0, 0, 0, 2],
[2, 2, 2, 2, 2, 2, 2]
]
Mouse.go(maze, {x: 1, y: 1}, {x: 5, y: 5}).each do |pt|
maze[pt[:x]][pt[:y]] = 1
end
if maze[5][5] == 0
puts "找不到出口"
end
maze.each do |row|
row.each do |block|
case block
when 0 then print " "
when 1 then print "◇"
when 2 then print "█"
end
end
puts
end
var mouse = function() {
function visit(maze, pt, end) {
if(isVisitable(maze, pt)) {
maze[pt.x][pt.y] = 1;
if(!isEnd(maze, end) && !tryOneOut(maze, pt, end)) {
maze[pt.x][pt.y] = 0;
}
}
return isEnd(maze, end);
}
function isVisitable(maze, pt) {
return maze[pt.x][pt.y] === 0;
}
function isEnd(maze, end) {
return maze[end.x][end.y] === 1;
}
function tryOneOut(maze, pt, end) {
return visit(maze, {x: pt.x, y: pt.y + 1}, end) ||
visit(maze, {x: pt.x + 1, y: pt.y}, end) ||
visit(maze, {x: pt.x, y: pt.y - 1}, end) ||
visit(maze, {x: pt.x - 1, y: pt.y}, end);
}
return function(maze, start, end) {
visit(maze, start, end);
return maze;
};
}();
var maze = mouse([[2, 2, 2, 2, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 2],
[2, 0, 2, 0, 2, 0, 2],
[2, 0, 0, 2, 0, 2, 2],
[2, 2, 0, 2, 0, 2, 2],
[2, 0, 0, 0, 0, 0, 2],
[2, 2, 2, 2, 2, 2, 2]],
{x: 1, y: 1}, {x: 5, y: 5});
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 tryOneOut maze pt end (pt:route)
else []
isVisitable maze pt route =
maze !! fst pt !! snd pt == 0 && not (pt `elem` route)
isEnd pt end = pt == end
tryOneOut maze pt end route =
visit maze (fst pt, snd pt + 1) end route `or'`
visit maze (fst pt + 1, snd pt) end route `or'`
visit maze (fst pt, snd pt - 1) end route `or'`
visit maze (fst pt - 1, snd pt) end route
or' expr1 expr2 = if route == [] then expr2 else route
where route = expr1
main = sequence [putStrLn row | row <- toSymbol maze \$ mouse maze start end]
where maze = [
[2, 2, 2, 2, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 2],
[2, 0, 2, 0, 2, 0, 2],
[2, 0, 0, 2, 0, 2, 2],
[2, 2, 0, 2, 0, 2, 2],
[2, 0, 0, 0, 0, 0, 2],
[2, 2, 2, 2, 2, 2, 2]]
start = (1, 1)
end = (5, 5)
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.
main(_) :-
Maze = [
[2, 2, 2, 2, 2, 2, 2],
[2, 0, 0, 0, 0, 0, 2],
[2, 0, 2, 0, 2, 0, 2],
[2, 0, 0, 2, 0, 2, 2],
[2, 2, 0, 2, 0, 2, 2],
[2, 0, 0, 0, 0, 0, 2],
[2, 2, 2, 2, 2, 2, 2]
],
find(Maze,
[5, 5],
[],
[1, 1],
Solution
),
printIt(Maze, Solution, 0).
