說明
老鼠走迷宮是遞迴求解的基本題型，我們在二維陣列中使用2表示迷宮牆壁，使用1來表示老鼠的行走路徑，試以程式求出由入口至出口的路徑。
解法
老鼠的走法有上、左、下、右四個方向，在每前進一格之後就選一個方向前進，無法前進時退回選擇下一個可前進方向，如此在陣列中依序測試四個方向，直到走到出口為止，這是遞迴的基本題，請直接看程式應就可以理解。
演算法
Procedure GO(maze[]) [
VISIT(maze, STARTI, STARTJ);
]
Procedure VISIT(maze[], i, j) [
maze[i][j] = 1;
IF(i == ENDI AND j == ENDJ)
success = TRUE;
IF(success != TRUE AND maze[i][j+1] == 0)
VISIT(maze, i, j+1);
IF(success != TRUE AND maze[i+1][j] == 0)
VISIT(maze, i+1, j);
IF(success != TRUE AND maze[i][j-1] == 0)
VISIT(maze, i, j-1);
if(success != TRUE AND maze[i-1][j] == 0)
VISIT(maze, i-1, j);
IF(success != TRUE)
maze[i][j] = 0;
]
#include <stdio.h>
#include <stdlib.h>
#define SIZE 7
#define START_I 1
#define START_J 1
#define END_I 5
#define END_J 5
int 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, 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, START_I, START_J) == 0)
printf("\n沒有找到出口！\n");
printMaze(maze);
return 0;
}
int visit(int maze[][SIZE], int i, int j) {
maze[i][j] = 1;
if(!isArrived(maze, i, j) && maze[i][j+1] == 0) visit(maze, i, j+1);
if(!isArrived(maze, i, j) && maze[i+1][j] == 0) visit(maze, i+1, j);
if(!isArrived(maze, i, j) && maze[i][j-1] == 0) visit(maze, i, j-1);
if(!isArrived(maze, i, j) && maze[i-1][j] == 0) visit(maze, i-1, j);
if(!isArrived(maze, i, j))
maze[i][j] = 0;
return isArrived(maze, i, j);
}
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);
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));
if(!maze.isArrived())
maze.empty(p);
}
private static void test(Maze maze, Point p) {
if(!maze.isArrived() && 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, 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}},
new Point(5, 5));
Mouse.go(maze, new Point(1, 1));
if(!maze.isArrived()) {
System.out.println("沒找到出口");
}
maze.print();
}
}
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)
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))
if not maze.isArrived():
maze.empty(p)
def __test(self, maze, p):
if not maze.isArrived() and maze.isEmpty(p):
self.go(maze, p)
maze = 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]
], Point(5, 5))
mouse = Mouse()
mouse.go(maze, Point(1, 1))
if not maze.isArrived():
print("找不到出口")
maze.print()
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)
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))
if(!maze.isArrived)
maze.empty(p)
}
private def test(maze: Maze, p: Point) {
if(!maze.isArrived && maze.isEmpty(p))
go(maze, p)
}
}
val maze = new Maze(
Array(
Array(2, 2, 2, 2, 2, 2, 2),
Array(2, 0, 0, 0, 0, 0, 2),
Array(2, 0, 2, 0, 2, 0, 2),
Array(2, 0, 0, 2, 0, 2, 2),
Array(2, 2, 0, 2, 0, 2, 2),
Array(2, 0, 0, 0, 0, 0, 2),
Array(2, 2, 2, 2, 2, 2, 2)
), Point(5, 5))
Mouse.go(maze, Point(1, 1))
if(!maze.isArrived)
println("沒找到出口")
maze.print()
# 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 "█".encode("Big5")
elsif @maze[i][j] == 1
print "◇".encode("Big5")
else
print " ".encode("Big5")
end
}
puts
}
end
end
class Mouse
def go(maze, p)
maze.step(p)
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))
if !maze.isArrived
maze.empty(p)
end
end
def test(maze, p)
if !maze.isArrived && maze.isEmpty(p)
go(maze, p)
end
end
private :test
end
maze = Maze.new([
[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]
], Point.new(5, 5))
mouse = Mouse.new
mouse.go(maze, Point.new(1, 1))
if !maze.isArrived
puts "找不到出口"
end
maze.layout
|
|