本篇介紹了用Java實現
老鼠走迷官演算法
工具/原料
win7
MyEclipse
jdk1.6
方法/步驟
1. 老鼠走迷官（一）
說明老鼠走迷宮是遞迴求解的基本題型，我們在二維陣列中使用2表示迷宮牆壁，使用1來表示老鼠的行走路徑，試以程式求出由入口至出口的路徑。解法老鼠的走法有上、左、下、右四個方向，在每前進一格之後就選一個方向前，無法前進時退回選擇下一個可前進方向，如此在陣列中依序測試四個方向，直到走到出口為止，這是遞迴的基本題，請直接看程式應就可以理解。
程式碼如下：
public class MainClass {
public static void main(String[] args) {
//一個二維陣列來表示迷宮，2表示牆壁，0表示通路。
//老鼠每走到一個格子的時候就將該位置的值置為1，表示老鼠的行走路徑包括這個格子。
int[][] maze = { { 2, 2, 2, 0, 2, 2, 2, 0, 0 },
{ 2, 0, 0, 0, 0, 0, 2, 0, 0 },
{ 2, 0, 2, 2, 2, 2, 2, 2, 2 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 2 },
{ 2, 0, 2, 2, 2, 2, 0, 2, 2 },
{ 2, 0, 2, 2, 0, 0, 0, 2, 2 },
{ 2, 0, 2, 2, 0, 2, 2, 0, 2 },
{ 2, 0, 2, 0, 0, 0, 0, 0, 0 },
{ 2, 0, 2, 2, 2, 2, 2, 2, 2 }
};
Map map = new Map(maze, new Point(7, 8));
MainClass.go(map, new Point(0, 3));
map.print();
}
public static void go(Map map, Point p) {
map.step(p);//走到哪裡則賦值為1
if (p.y < map.maze[0].length - 1) {
test(map, new Point(p.x, p.y + 1));
}
if (p.x < map.maze.length - 1) {
test(map, new Point(p.x + 1, p.y));
}
if (p.y >= 1) {
test(map, new Point(p.x, p.y - 1));
}
if (p.x >= 1) {
test(map, new Point(p.x - 1, p.y));
}
if (!map.isArrived())
map.empty(p);
}
public static void test(Map map, Point p) {
if (!map.isArrived() && map.isEmpty(p)) {
go(map, p);
}
}
}
class Point {
int x;
int y;
public Point(int x1, int y1) {
x = x1;
y = y1;
}
}
class Map {
int[][] maze;
Point end; // 終點
public Map(int[][] maze, Point end) {
this.maze = maze;
this.end = end;
}
// 是否到達終點
public boolean isArrived() {
return maze[end.x][end.y] == 1;
}
// 當前這一格是否可行
public boolean isEmpty(Point p) {
return maze[p.x][p.y] == 0;
}
// 可以理解為當經過Point p 路線不對，把老鼠走過的痕跡抹去，置0
public void empty(Point p) {
maze[p.x][p.y] = 0;
}
// 走到Point p 置1
public void step(Point p) {
maze[p.x][p.y] = 1;
}
// 列印地圖，含老鼠走過的路徑
public 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] == 0) {
System.out.print(" ");
} else if (maze[i][j] == 1) {
System.out.print("1");
}
System.out.println();
}
}
}
結果如下：
2.老鼠走迷官（二）
說明由於迷宮的設計，老鼠走迷宮的入口至出口路徑可能不只一條，如何求出所有的路徑呢？解法求所有路徑看起來複雜但其實更簡單，只要在老鼠走至出口時顯示經過的路徑，然後退回上一格重新選擇下一個位置繼續遞迴就可以了，比求出單一路徑還簡單，我們的程式只要作一點修改就可以了。
程式碼如下：
public class MainClass {
public static void main(String[] args) {
int[][] maze={{2,2,2,0,2,2,2,0,0},
{2,0,0,0,0,0,2,0,0},
{2,0,2,2,2,0,2,2,2},
{0,0,0,0,0,0,0,0,2},
{2,0,2,2,2,2,0,2,2},
{2,0,2,2,0,0,0,2,2},
{2,0,2,2,0,2,2,0,2},
{2,0,2,0,0,0,0,0,0},
{2,0,2,2,2,2,2,2,2}
};
Map map=new Map(maze, new Point(7, 8));
MainClass.go(map, new Point(0,3));
//map.print();
}
public static void go(Map map,Point p){
map.step(p);
if(map.isArrived())
{
map.print();
map.maze[map.end.x][map.end.y]=0;
}
if(p.y
{
test(map,new Point(p.x, p.y+1));
}
if(p.x
{
test(map,new Point(p.x+1, p.y));
}
if(p.y>=1)
{
test(map,new Point(p.x, p.y-1));
}
if(p.x>=1)
{
test(map,new Point(p.x-1, p.y));
}
map.empty(p);
}
public static void test(Map map,Point p){
if(!map.isArrived() && map.isEmpty(p)){
go(map,p);
}
}
}
class Point{
int x;
int y;
public Point(int x1,int y1){
x=x1;
y=y1;
}
}
class Map{
int[][] maze;
Point end; //終點
public Map(int[][] maze,Point end){
this.maze=maze;
this.end=end;
}
//是否到達終點
public boolean isArrived(){
return maze[end.x][end.y]==1;
}
//當前這一格是否可行
public boolean isEmpty(Point p){
return maze[p.x][p.y]==0;
}
//可以理解為當經過Point p 無法走到終點時，把老鼠走過的痕跡抹去，表示最終的走法不含p
public void empty(Point p){
maze[p.x][p.y]=0;
}
//走到Point p
public void step(Point p){
maze[p.x][p.y]=1;
}
//列印地圖，含老鼠走過的路徑
public void print(){
for(int i=0;i
{
for(int j=0;j
if(maze[i][j]==2){
System.out.print("█");
}else if(maze[i][j]==0){
System.out.print(" ");
}else if(maze[i][j]==1){
System.out.print("1");
}
System.out.println();
}
System.out.println();
}
}
結果如下：
