# 老鼠走迷官（一）

## 演算法

``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] == 0           IF !(VISIT(maze, i, j + 1, end_i, end_j) OR                 VISIT(maze, i + 1, j, end_i, end_j) OR                VISIT(maze, i, j - 1, end_i, end_j) OR                 VISIT(maze, i - 1, j, end_i, end_j))               maze[i][j] = 0    RETURN maze[end_i][end_j] == 1``

``````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 visit(st, ed) {
if not this.get(st.x, st.y) {
this.set(st.x, st.y, 1)
if not this.get(ed.x, ed.y) and not this.tryOneOut(st, ed) {
this.set(st.x, st.y, 0)
}
}
return this.get(ed.x, ed.y)
}

def tryOneOut(st, ed) {
(return this.visit(pt(st.x, st.y + 1), ed) or
this.visit(pt(st.x + 1, st.y), ed) or
this.visit(pt(st.x, st.y - 1), ed) or
this.visit(pt(st.x - 1, st.y), ed))

}

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, 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 not maze.visit(pt(1, 1), pt(5, 5)) {
println('沒有找到出口！')
}

maze.print()``````

``#include <stdio.h>#include <stdlib.h>#define SIZE 7typedef struct {    int x;     int y;} Point;Point pt(int, int);int visit(int[][SIZE], Point, Point);void print(int[][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, pt(1, 1), pt(5, 5))) {        printf("\n沒有找到出口！\n");     }    print(maze);        return 0; }Point pt(int x, int y) {    Point p = {x, y};    return p;}int visit(int maze[][SIZE], Point start, Point end) {    if(!maze[start.x][start.y]) {         maze[start.x][start.y] = 1;         if(!maze[end.x][end.y] &&             !(visit(maze, pt(start.x, start.y + 1), end) ||               visit(maze, pt(start.x + 1, start.y), end) ||              visit(maze, pt(start.x, start.y - 1), end) ||               visit(maze, pt(start.x - 1, start.y), end))) {                 maze[start.x][start.y] = 0;         }    }    return maze[end.x][end.y];    }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;    }}public class Mouse {    public static int[][] go(int[][] maze, Point start, Point end) {        visit(maze, start, end);        return maze;    }        public static boolean visit(int[][] maze, Point pt, Point end) {        if(isVisitable(maze, pt)) {            maze[pt.x][pt.y] = 1;            if(!isEnd(maze, end) && !tryOneOut(maze, pt, end)) {                maze[pt.x][pt.y] = 0;            }        }        return isEnd(maze, end);    }    public 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 boolean tryOneOut(int[][] maze, Point pt, Point end) {        return visit(maze, new Point(pt.x, pt.y + 1), end) ||               visit(maze, new Point(pt.x + 1, pt.y), end) ||               visit(maze, new Point(pt.x, pt.y - 1), end) ||               visit(maze, new Point(pt.x - 1, pt.y), end);    }        public static void main(String[] args) {        int[][] 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}};                                           for(int[] row : Mouse.go(maze, new Point(1, 1), new Point(5, 5))) {            for(int block : row) switch(block) {                case 0: out.print("  "); break;                case 1: out.print("◇"); break;                case 2: out.print("█");            }            out.println();        }        out.println(Mouse.isEnd(maze, new Point(5, 5))                     ? "找到出口" : "沒有找到出口！");    }} ``

``class Mouse:    @staticmethod    def go(maze, start, end):        route = []        Mouse.visit(maze, start, end, route)        return route        @staticmethod    def visit(maze, pt, end, route):        if Mouse.isVisitable(maze, pt, route):            route.append(pt)            if not Mouse.isEnd(route, end) and \               not Mouse.tryOneOut(maze, pt, end, route):                route.pop()        return Mouse.isEnd(route, end)        @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            @staticmethod    def tryOneOut(maze, pt, end, route):        return Mouse.visit(maze, (pt[0], pt[1] + 1), end, route) or \               Mouse.visit(maze, (pt[0] + 1, pt[1]), end, route) or \               Mouse.visit(maze, (pt[0], pt[1] - 1), end, route) or \               Mouse.visit(maze, (pt[0] - 1, pt[1]), end, route)               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]]        for pt in Mouse.go(maze, (1, 1), (5, 5)):    maze[pt[0]][pt[1]] = 1if maze[5][5] == 0:    print("找不到出口")for row in maze:    for block in row:        {            0 : lambda: print("  ", end=""),            1 : lambda: print("◇", end=""),            2 : lambda: print("█",end=""),        }[block]()    print()``

``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[Point] = {        if(isVisitable(maze, pt, route)) {            if(isEnd(pt, end)) end::route             else tryOneOut(maze, pt, 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        def tryOneOut(maze: List[List[Int]], pt: Point,                   end: Point, route: List[Point]) = {        or(visit(maze, Point(pt.x, pt.y + 1), end, route)) {             or(visit(maze, Point(pt.x + 1, pt.y), end, route)) {                or(visit(maze, Point(pt.x, pt.y - 1), end, route)) {                    visit(maze, Point(pt.x - 1, pt.y), end, route)                }            }        }    }        def or(expr1: => List[Point])(expr2: => List[Point]) = {        val route = expr1        if(route == Nil) expr2 else route        }}val maze = List(               List(2, 2, 2, 2, 2, 2, 2),                List(2, 0, 0, 0, 0, 0, 2),                List(2, 0, 2, 0, 2, 0, 2),                List(2, 0, 0, 2, 0, 2, 2),                List(2, 2, 0, 2, 0, 2, 2),                List(2, 0, 0, 0, 0, 0, 2),                List(2, 2, 2, 2, 2, 2, 2)           )val route = Mouse.go(maze, Point(1, 1), Point(5, 5))if(!route.contains(Point(5, 5))) {    println("找不到出口")}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)        route = []        visit(maze, start, goal, route)        route    end        def self.visit(maze, pt, goal, route)        if isVisitable(maze, pt, route)            route << pt            if not isGoal(route, goal) and                not tryOneOut(maze, pt, goal, route)                route.pop            end        end        isGoal(route, goal)    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        def self.tryOneOut(maze, pt, goal, route)        visit(maze, {x: pt[:x], y: pt[:y] + 1}, goal, route) or        visit(maze, {x: pt[:x] + 1, y: pt[:y]}, goal, route) or        visit(maze, {x: pt[:x], y: pt[:y] - 1}, goal, route) or        visit(maze, {x: pt[:x] - 1, y: pt[:y]}, goal, route)    endendmaze = [          [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]       ]       Mouse.go(maze, {x: 1, y: 1}, {x: 5, y: 5}).each do |pt|    maze[pt[:x]][pt[:y]] = 1endif maze[5][5] == 0    puts "找不到出口"endmaze.each do |row|    row.each do |block|        case block            when 0 then print "  "            when 1 then print "◇"            when 2 then print "█"        end    end    putsend``

``var mouse = function() {    function visit(maze, pt, end) {        if(isVisitable(maze, pt)) {            maze[pt.x][pt.y] = 1;            if(!isEnd(maze, end) && !tryOneOut(maze, pt, end)) {                maze[pt.x][pt.y] = 0;            }        }        return isEnd(maze, end);    }        function isVisitable(maze, pt) {        return maze[pt.x][pt.y] === 0;    }        function isEnd(maze, end) {        return maze[end.x][end.y] === 1;    }        function tryOneOut(maze, pt, end) {        return visit(maze, {x: pt.x, y: pt.y + 1}, end) ||               visit(maze, {x: pt.x + 1, y: pt.y}, end) ||               visit(maze, {x: pt.x, y: pt.y - 1}, end) ||               visit(maze, {x: pt.x - 1, y: pt.y}, end);    }        return function(maze, start, end) {        visit(maze, start, end);        return maze;    };    }();var maze = mouse([[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]],                  {x: 1, y: 1}, {x: 5, y: 5});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 tryOneOut maze pt end (pt:route)                                    else []                                              isVisitable maze pt route =               maze !! fst pt !! snd pt == 0 && not (pt `elem` route)                        isEnd pt end = pt == end                    tryOneOut maze pt end route =               visit maze (fst pt, snd pt + 1) end route `or'`              visit maze (fst pt + 1, snd pt) end route `or'`              visit maze (fst pt, snd pt - 1) end route `or'`              visit maze (fst pt - 1, snd pt) end route                        or' expr1 expr2 = if route == [] then expr2 else route              where route = expr1    main = sequence [putStrLn row | row <- toSymbol maze \\$ mouse maze start end]    where 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]]          start = (1, 1)          end = (5, 5)          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.

main(_) :-
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]
],
find(Maze,
[5, 5],
[],
[1, 1],
Solution
),
printIt(Maze, Solution, 0).``````