老鼠走迷官(二)


 說明

由於迷宮的設計,老鼠走迷宮的入口至出口路徑可能不只一條,如何求出所有的路徑呢?

解法

求所有路徑看起來複雜但其實更簡單,只要在老鼠走至出口時顯示經過的路徑,然後退回上一格重新選擇下一個位置繼續遞迴就可以了,比求出單一路徑還簡 單,我們的程式只要作一點修改就可以了。

演算法

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

實作:C    Java    Python    Scala    Ruby    JavaScript    Haskell    Prolog

  • C
#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");
}
}

  • Java
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();
}
}
);
}
}

  • Python
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)

  • Scala
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()
}
)

  • Ruby
#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

  • JavaScript
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);
});

  • Haskell
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).