mousegomaze.htm
来自「“常见程式演算”主要收集一些常见的程式练习题目」· HTM 代码 · 共 81 行
HTM
81 行
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>老鼠走迷官（一）</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 老鼠走迷官（一）</a></h1>
<h2> 说明</h2>
老鼠走迷宫是递回求解的基本题型，我们在二维阵列中使用2表示迷宫墙壁，使用1来表示老鼠的行走路径，试以程式求出由入口至出口的路径。<br>
<h2>解法</h2>
老鼠的走法有上、左、下、右四个方向，在每前进一格之后就选一个方向前进，无法前进时退回选择下一个可前进方向，如此在阵列中依序测试四个方向，直到走到出口为止，这是递回的基本题，请直接看程式应就可以理解。 <br>
<br>
<h2> 演算法</h2>
<pre>Procedure GO(maze[]) [<br> VISIT(maze, STARTI, STARTJ);<br>]<br> <br>Procedure VISIT(maze[], i, j) [<br> maze[i][j] = 1; <br><br> IF(i == ENDI AND j == ENDJ) <br> success = TRUE; <br><br> IF(success != TRUE AND maze[i][j+1] == 0)<br> VISIT(maze, i, j+1); <br> IF(success != TRUE AND maze[i+1][j] == 0)<br> VISIT(maze, i+1, j); <br> IF(success != TRUE AND maze[i][j-1] == 0)<br> VISIT(maze, i, j-1); <br> if(success != TRUE AND maze[i-1][j] == 0)<br> VISIT(maze, i-1, j); <br><br> IF(success != TRUE) <br> maze[i][j] = 0; <br>] <br></pre>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h><br>#include <stdlib.h> <br><br>int visit(int, int); <br><br>int maze[7][7] = {{2, 2, 2, 2, 2, 2, 2}, <br> {2, 0, 0, 0, 0, 0, 2}, <br> {2, 0, 2, 0, 2, 0, 2}, <br> {2, 0, 0, 2, 0, 2, 2}, <br> {2, 2, 0, 2, 0, 2, 2}, <br> {2, 0, 0, 0, 0, 0, 2}, <br> {2, 2, 2, 2, 2, 2, 2}}; <br><br>int startI = 1, startJ = 1; // 入口<br>int endI = 5, endJ = 5; // 出口<br>int success = 0;<br><br>int main(void) { <br> int i, j; <br><br> printf("显示迷宫：\n"); <br> for(i = 0; i < 7; i++) { <br> for(j = 0; j < 7; j++) <br> if(maze[i][j] == 2) <br> printf("█"); <br> else <br> printf(" "); <br> printf("\n"); <br> } <br><br> if(visit(startI, startJ) == 0)<br> printf("\n没有找到出口！\n"); <br> else { <br> printf("\n显示路径：\n"); <br> for(i = 0; i < 7; i++) { <br> for(j = 0; j < 7; j++) { <br> if(maze[i][j] == 2) <br> printf("█"); <br> else if(maze[i][j] == 1) <br> printf("◇"); <br> else <br> printf(" "); <br> } <br> printf("\n"); <br> } <br> } <br><br> return 0; <br>} <br><br>int visit(int i, int j) { <br> maze[i][j] = 1; <br><br> if(i == endI && j == endJ)<br> success = 1; <br><br> if(success != 1 && maze[i][j+1] == 0) visit(i, j+1); <br> if(success != 1 && maze[i+1][j] == 0) visit(i+1, j); <br> if(success != 1 && maze[i][j-1] == 0) visit(i, j-1); <br> if(success != 1 && maze[i-1][j] == 0) visit(i-1, j); <br><br> if(success != 1) <br> maze[i][j] = 0; <br> <br> return success; <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>public class Mouse {<br> private int startI, startJ; // 入口 <br> private int endI, endJ; // 出口<br> private boolean success = false;<br> <br> public static void main(String[] args) {<br> int[][] maze = {{2, 2, 2, 2, 2, 2, 2}, <br> {2, 0, 0, 0, 0, 0, 2}, <br> {2, 0, 2, 0, 2, 0, 2}, <br> {2, 0, 0, 2, 0, 2, 2}, <br> {2, 2, 0, 2, 0, 2, 2}, <br> {2, 0, 0, 0, 0, 0, 2}, <br> {2, 2, 2, 2, 2, 2, 2}};<br> <br> System.out.println("显示迷宫："); <br> for(int i = 0; i < maze.length; i++) { <br> for(int j = 0; j < maze[0].length; j++) <br> if(maze[i][j] == 2) <br> System.out.print("█"); <br> else <br> System.out.print(" "); <br> System.out.println(); <br> }<br><br> Mouse mouse = new Mouse();<br> mouse.setStart(1, 1);<br> mouse.setEnd(5, 5);<br> <br> if(!mouse.go(maze)) {<br> System.out.println("\n没有找到出口！");<br> }<br> else {<br> System.out.println("\n找到出口！");<br> for(int i = 0; i < maze.length; i++) { <br> for(int j = 0; j < maze[0].length; j++) { <br> if(maze[i][j] == 2) <br> System.out.print("█"); <br> else if(maze[i][j] == 1) <br> System.out.print("◇"); <br> else <br> System.out.print(" "); <br> } <br> System.out.println(); <br> } <br> }<br> }<br> <br> public void setStart(int i, int j) {<br> this.startI = i;<br> this.startJ = j;<br> }<br> <br> public void setEnd(int i, int j) {<br> this.endI = i;<br> this.endJ = j;<br> }<br> <br> public boolean go(int[][] maze) {<br> return visit(maze, startI, startJ);<br> }<br> <br> private boolean visit(int[][] maze, int i, int j) {<br> maze[i][j] = 1; <br><br> if(i == endI && j == endJ) <br> success = true; <br><br> if(!success && maze[i][j+1] == 0) <br> visit(maze, i, j+1); <br> if(!success && maze[i+1][j] == 0)<br> visit(maze, i+1, j); <br> if(!success && maze[i][j-1] == 0)<br> visit(maze, i, j-1); <br> if(!success && maze[i-1][j] == 0)<br> visit(maze, i-1, j); <br><br> if(!success) <br> maze[i][j] = 0; <br> <br> return success; <br> }<br>} </pre>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?