說明
由於迷宮的設計，老鼠走迷宮的入口至出口路徑可能不只一條，如何求出所有的路徑呢？
解法
求所有路徑看起來複雜但其實更簡單，只要在老鼠走至出口時顯示經過的路徑，然後退回上一格重新選擇下一個位置繼續遞迴就可以了，比求出單一路徑還簡單，我們的程式只要作一點修改就可以了。
演算法
Procedure GO(maze[]) [
VISIT(maze, STARTI, STARTJ);
]
Procedure VISIT(maze[], i, j) [
maze[i][j] = 1;
IF(i == ENDI AND j == ENDJ) [
// FIND A ROUTE, PRINT THE ROUTE
]
IF(maze[i][j+1] == 0)
VISIT(maze, i, j+1);
IF(maze[i+1][j] == 0)
VISIT(maze, i+1, j);
IF(maze[i][j-1] == 0)
VISIT(maze, i, j-1);
if(maze[i-1][j] == 0)
VISIT(maze, i-1, j);
maze[i][j] = 0;
]
#include <stdio.h>
#include <stdlib.h>
#define SIZE 9
#define START_I 1
#define START_J 1
#define END_I 7
#define END_J 7
void visit(int maze[][SIZE], int, int);
int isArrived(int maze[][SIZE], int, int);
void printMaze(int maze[][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, START_I, START_J);
return 0;
}
void visit(int maze[][SIZE], int i, int j) {
maze[i][j] = 1;
if(isArrived(maze, i, j)) {
printMaze(maze);
}
if(maze[i][j+1] == 0) visit(maze, i, j+1);
if(maze[i+1][j] == 0) visit(maze, i+1, j);
if(maze[i][j-1] == 0) visit(maze, i, j-1);
if(maze[i-1][j] == 0) visit(maze, i-1, j);
maze[i][j] = 0;
}
int isArrived(int maze[][SIZE], int i, int j) {
return maze[END_I][END_J];
}
void printMaze(int maze[][SIZE]) {
int i, j;
for(i = 0; i < SIZE; i++) {
for(j = 0; j < SIZE; j++) {
if(maze[i][j] == 2)
printf("█");
else if(maze[i][j] == 1)
printf("◇");
else
printf(" ");
}
printf("\n");
}
}
class Point {
final int x;
final int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
class Maze {
private int[][] maze;
private Point end;
Maze(int[][] maze, Point end) {
this.maze = maze;
this.end = end;
}
boolean isArrived() {
return maze[end.x][end.y] == 1;
}
boolean isEmpty(Point p) { return maze[p.x][p.y] == 0; }
void step(Point p) { maze[p.x][p.y] = 1; }
void empty(Point p) { maze[p.x][p.y] = 0; }
void print() {
for(int i = 0; i < maze.length; i++) {
for(int j = 0; j < maze[0].length; j++) {
if(maze[i][j] == 2)
System.out.print("█");
else if(maze[i][j] == 1)
System.out.print("◇");
else
System.out.print(" ");
}
System.out.println();
}
}
}
public class Mouse {
public static void go(Maze maze, Point p) {
maze.step(p);
if(maze.isArrived()) {
maze.print();
}
test(maze, new Point(p.x, p.y + 1));
test(maze, new Point(p.x + 1, p.y));
test(maze, new Point(p.x, p.y - 1));
test(maze, new Point(p.x - 1, p.y));
maze.empty(p);
}
private static void test(Maze maze, Point p) {
if(maze.isEmpty(p))
go(maze, p);
}
public static void main(String[] args) {
Maze maze = new Maze(
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(7, 7));
Mouse.go(maze, new Point(1, 1));
}
}
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
class Maze:
def __init__(self, maze, end):
self.maze = maze
self.end = end
def isArrived(self):
return self.maze[self.end.x][self.end.y] == 1
def isEmpty(self, p):
return self.maze[p.x][p.y] == 0
def step(self, p):
self.maze[p.x][p.y] = 1
def empty(self, p):
self.maze[p.x][p.y] = 0
def print(self):
for i in range(len(self.maze)):
for j in range(len(self.maze[0])):
if self.maze[i][j] == 2:
print("█",end="")
elif self.maze[i][j] == 1:
print("◇", end="")
else:
print(" ", end="")
print()
class Mouse:
def go(self, maze, p):
maze.step(p)
if maze.isArrived():
maze.print()
self.__test(maze, Point(p.x, p.y + 1))
self.__test(maze, Point(p.x + 1, p.y))
self.__test(maze, Point(p.x, p.y - 1))
self.__test(maze, Point(p.x - 1, p.y))
maze.empty(p)
def __test(self, maze, p):
if maze.isEmpty(p):
self.go(maze, p)
maze = 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]
], Point(7, 7))
mouse = Mouse()
mouse.go(maze, Point(1, 1))
case class Point(x: Int, y: Int)
class Maze(maze: Array[Array[Int]], end: Point) {
def isArrived() = maze(end.x)(end.y) == 1
def isEmpty(p: Point) = maze(p.x)(p.y) == 0
def step(p: Point) { maze(p.x)(p.y) = 1 }
def empty(p: Point) { maze(p.x)(p.y) = 0 }
def print() {
for(i <- 0 until maze.length) {
for(j <- 0 until maze(0).length) {
printf(if(maze(i)(j) == 2) "█"
else if(maze(i)(j) == 1) "◇"
else " ")
}
println()
}
}
}
object Mouse {
def go(maze: Maze, p: Point) {
maze.step(p)
if(maze.isArrived)
maze.print()
test(maze, Point(p.x, p.y + 1))
test(maze, Point(p.x + 1, p.y))
test(maze, Point(p.x, p.y - 1))
test(maze, Point(p.x - 1, p.y))
maze.empty(p)
}
private def test(maze: Maze, p: Point) {
if(maze.isEmpty(p))
go(maze, p)
}
}
val maze = new Maze(
Array(
Array(2, 2, 2, 2, 2, 2, 2, 2, 2),
Array(2, 0, 0, 0, 0, 0, 0, 0, 2),
Array(2, 0, 2, 2, 0, 2, 2, 0, 2),
Array(2, 0, 2, 0, 0, 2, 0, 0, 2),
Array(2, 0, 2, 0, 2, 0, 2, 0, 2),
Array(2, 0, 0, 0, 0, 0, 2, 0, 2),
Array(2, 2, 0, 2, 2, 0, 2, 2, 2),
Array(2, 0, 0, 0, 0, 0, 0, 0, 2),
Array(2, 2, 2, 2, 2, 2, 2, 2, 2)
), Point(7, 7))
Mouse.go(maze, Point(1, 1))
# encoding: Big5
class Point
attr_accessor :x, :y
def initialize(x, y)
@x = x
@y = y
end
end
class Maze
def initialize(maze, goal)
@maze = maze
@goal = goal
end
def isArrived
@maze[@goal.x][@goal.y] == 1
end
def isEmpty(p)
@maze[p.x][p.y] == 0
end
def step(p)
@maze[p.x][p.y] = 1
end
def empty(p)
@maze[p.x][p.y] = 0
end
def layout()
@maze.length.times { |i|
@maze[0].length.times { |j|
if @maze[i][j] == 2
print "█"
elsif @maze[i][j] == 1
print "◇"
else
print " "
end
}
puts
}
end
end
class Mouse
def go(maze, p)
maze.step(p)
if maze.isArrived
maze.layout
end
test(maze, Point.new(p.x, p.y + 1))
test(maze, Point.new(p.x + 1, p.y))
test(maze, Point.new(p.x, p.y - 1))
test(maze, Point.new(p.x - 1, p.y))
maze.empty(p)
end
def test(maze, p)
if maze.isEmpty(p)
go(maze, p)
end
end
private :test
end
maze = Maze.new([
[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]
], Point.new(7, 7))
mouse = Mouse.new
mouse.go(maze, Point.new(1, 1))
|
|