# 老鼠走迷官（二）

## 演算法

``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``

``````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 goalOrTry(st, ed) {
if this.get(ed.x, ed.y) {
this.print()
}
else {
this.visit(pt(st.x, st.y + 1), ed)
this.visit(pt(st.x + 1, st.y), ed)
this.visit(pt(st.x, st.y - 1), ed)
this.visit(pt(st.x - 1, st.y), ed)
}
}

def visit(st, ed) {
if not this.get(st.x, st.y) {
this.set(st.x, st.y, 1)
this.goalOrTry(st, ed)
this.set(st.x, st.y, 0)
}
}

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, 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]
]))

maze.visit(pt(1, 1), pt(7, 7))``````

``#include <stdio.h>#include <stdlib.h>#define SIZE 9typedef 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");     }     }``

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

``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 routedef 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)``

``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()    })``

``#encoding: Big5class 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    endendmaze = [           [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    endend``

``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);      });``

``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).``````