1 /*

  2  *内容；老鼠走迷宫I

  3  *时间；2/16/2013

  4  */

  5

  6 #include <stdio.h>

  7

  8 // 注：二维数组，根据编译器采取的策略不同，起点或终点位置会有所不同

  9 //     既编译器可能采取“按行优先”或者是“按列优先”这两种不同的策略

 10

 11 //终点位置

 12 #define END_I 7

 13 #define END_J 1

 14

 15 //迷宫为全局变量

 16 //初始化迷宫，用2来表示墙壁、1表示路径

 17 int g_maze[9][9] = { {2, 2, 2, 2, 2, 2, 2, 2, 2},

 18                        {2, 0, 0, 2, 0, 2, 0, 0, 2},//起点位置(1,1)

 19                        {2, 0, 2, 0, 0, 0, 0, 2, 2},

 20                        {2, 0, 0, 0, 2, 2, 0, 0, 2},

 21                        {2, 2, 2, 0, 0, 0, 2, 0, 2},

 22                        {2, 0, 0, 0, 2, 0, 2, 0, 2},

 23                        {2, 2, 2, 2, 0, 2, 0, 0, 2},

 24                        {2, 0, 0, 0, 0, 0, 0, 2, 2},//终点位置(7, 1)

 25                        {2, 2, 2, 2, 2, 2, 2, 2, 2},

 26                      };

 27

 28 bool g_sucess = false;//全局变量，用来确保是否到达终点。

 29

 30 //打印迷宫

 31 void printMaze(int *maze, int mazeWidth, int mazeHeight)

 32 {

 33     int mazeSize = 0;

 34     //将传进来二位数组的长度相乘确保能够完全遍历完数组

 35     mazeSize = mazeWidth * mazeHeight;

 36     for (int i = 0; i < mazeSize; ++i)

 37     {

 38         if ( (i%mazeWidth) == 0)

 39         {

 40             printf ("\n");

 41         }

 42         if ( *maze == 2 )//2表示墙壁，墙壁用X表示

 43         {

 44             printf ("X");

 45         }

 46         else if ( *maze == 1 )//1表示走过的路径，用“.”表示

 47         {

 48             printf (".");

 49         }

 50         else if ( *maze == 3 )//终点位置打印笑脸

 51         {

 52             putchar(1);

 53         }

 54         else//0表示可走路径，用“o”来表示

 55         {

 56             printf ("o");

 57         }

 58         maze++;

 59     }

 60     printf ("\n\n");

 61 }

 62

 63 bool visit(int i, int j)

 64 {

 65     g_maze[i][j] = 1;

 66     if ( (i==END_I) && (j==END_J) )

 67     {

 68         g_maze[i][j] = 3;

 69         g_sucess = true;

 70         return g_sucess;

 71     }

 72     else

 73     {

 74         //向下走

 75         if ( (!g_sucess) && (g_maze[i][j+1]==0) )

 76         {

 77             visit(i, j+1);

 78         }

 79         //向右走

 80         if ( (!g_sucess) && (g_maze[i+1][j]==0) )

 81         {

 82             visit(i+1, j);

 83         }

 84         //向上走

 85         if ( (!g_sucess) && (g_maze[i][j-1]==0) )

 86         {

 87             visit(i, j-1);

 88         }

 89         //向左走

 90         if ( (!g_sucess) && (g_maze[i-1][j]==0) )

 91         {

 92             visit(i-1, j);

 93         }

 94         if (!g_sucess)//如果还没有找到出口则说明该路线是死路，恢复该点原状

 95         {

 96             g_maze[i][j] = 0;

 97         }

 98         return g_sucess;

 99     }

100 }

101

102

103

104 int main()

105 {

106

107     printf ("\t显示迷宫：\n\n");

108     printMaze(&(g_maze[0][0]), 9, 9);

109     if ( visit(1,1) )//把起点位置传进去

110     {

111         printf ("已找到出口，打印路径:\n\n");

112         printMaze(&(g_maze[0][0]), 9, 9);

113     }

114     else

115     {

116         printf ("没有找到出口！");

117     }

118     return 1;

119 }

 1 public class MouseMaze {

 2     int[][] g_maze = {

 3             {2, 2, 2, 2, 2, 2, 2, 2, 2},

 4             {2, 0, 0, 2, 0, 2, 0, 0, 2},//起点位置(1,1)

 5             {2, 0, 2, 0, 0, 0, 0, 2, 2},

 6             {2, 0, 0, 0, 2, 2, 0, 0, 2},

 7             {2, 2, 2, 0, 0, 0, 2, 0, 2},

 8             {2, 0, 0, 0, 2, 0, 2, 0, 2},

 9             {2, 2, 2, 2, 0, 2, 0, 0, 2},

10             {2, 0, 0, 0, 0, 0, 0, 2, 2},//终点位置(7, 1)

11             {2, 2, 2, 2, 2, 2, 2, 2, 2},

12           };

13     boolean g_sucess = false;

14     int END_i = 7;

15     int END_j = 1;

16

17     public MouseMaze(){

18     }

19

20     public void printMaze(){

21         for(int i = 0; i < g_maze.length; i++){

22             for(int j = 0; j < g_maze[i].length; j++){

23                 if(g_maze[i][j] == 2){

24                     System.out.print('X');

25                 }

26                 else if (g_maze[i][j] == 0) {

27                     System.out.print('o');

28                 }

29                 else if(g_maze[i][j] == 1)//走过的路径标记为1

30                     System.out.print('.');

31                 if(j == g_maze[i].length - 1){

32                     System.out.print('\n');

33                 }

34             }

35         }

36     }

37     //

38     public void visit(int i, int j){

39         //将走过的路径标为 1

40         g_maze[i][j] = 1;

41         //向上访问

42         if(i == END_i && j == END_j){

43             g_sucess = true;

44             return;

45         }

46         if(g_maze[i-1][j] == 0 && !g_sucess ){

47             visit(i - 1, j);

48         }

49         if(g_maze[i+1][j] == 0 && !g_sucess){

50             visit(i+1, j);

51         }

52         if(g_maze[i][j-1] == 0 && !g_sucess){

53             visit(i, j-1);

54         }

55         if(g_maze[i][j+1] == 0 && !g_sucess){

56             visit(i, j+1);

57         }

58         if(!g_sucess){

59             g_maze[i][j] = 0;

60         }

61     }

62     public static void main(String[] args) {

63         MouseMaze mm = new MouseMaze();

64         mm.printMaze();

65         mm.visit(1, 1);

66         System.out.println("-----------------");

67         mm.printMaze();

68     }

69 }