以一個m×n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。
（1） 根據(jù)二維數(shù)組，輸出迷宮的圖形。
（2） 探索迷宮的四個方向：right為向右，down向下，left向左，up向上，輸出從入口到出口的行走路徑。
例子：
左上角（1，1）為入口，右下角（8，9）為出口。
可使用回溯方法，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設(shè)定的迷宮沒有通路。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
import java.util.*;class position{ public position(){ } public position(int row, int col){ this.col = col; this.row = row; } public string tostring(){ return "(" + row + " ," + col + ")"; } int row; int col;}class maze{ public maze(){ maze = new int[15][15]; stack = new stack<position>(); p = new boolean[15][15]; } /* * 構(gòu)造迷宮 */ public void init(){ scanner scanner = new scanner(system.in); system.out.println("請輸入迷宮的行數(shù)"); row = scanner.nextint(); system.out.println("請輸入迷宮的列數(shù)"); col = scanner.nextint(); system.out.println("請輸入" + row + "行" + col + "列的迷宮"); int temp = 0; for(int i = 0; i < row; ++i) { for(int j = 0; j < col; ++j) { temp = scanner.nextint(); maze[i][j] = temp; p[i][j] = false; } } } /* * 回溯迷宮，查看是否有出路 */ public void findpath(){ // 給原始迷宮的周圍家一圈圍墻 int temp[][] = new int[row + 2][col + 2]; for(int i = 0; i < row + 2; ++i) { for(int j = 0; j < col + 2; ++j) { temp[0][j] = 1; temp[row + 1][j] = 1; temp[i][0] = temp[i][col + 1] = 1; } } // 將原始迷宮復(fù)制到新的迷宮中 for(int i = 0; i < row; ++i) { for(int j = 0; j < col; ++j) { temp[i + 1][j + 1] = maze[i][j]; } } // 從左上角開始按照順時針開始查詢 int i = 1; int j = 1; p[i][j] = true; stack.push(new position(i, j)); while (!stack.empty() && (!(i == (row) && (j == col)))) { if ((temp[i][j + 1] == 0) && (p[i][j + 1] == false)) { p[i][j + 1] = true; stack.push(new position(i, j + 1)); j++; } else if ((temp[i + 1][j] == 0) && (p[i + 1][j] == false)) { p[i + 1][j] = true; stack.push(new position(i + 1, j)); i++; } else if ((temp[i][j - 1] == 0) && (p[i][j - 1] == false)) { p[i][j - 1] = true; stack.push(new position(i, j - 1)); j--; } else if ((temp[i - 1][j] == 0) && (p[i - 1][j] == false)) { p[i - 1][j] = true; stack.push(new position(i - 1, j)); i--; } else { stack.pop(); if(stack.empty()){ break; } i = stack.peek().row; j = stack.peek().col; } } stack<position> newpos = new stack<position>(); if (stack.empty()) { system.out.println("沒有路徑"); } else { system.out.println("有路徑"); system.out.println("路徑如下："); while (!stack.empty()) { position pos = new position(); pos = stack.pop(); newpos.push(pos); } } /* * 圖形化輸出路徑 * */ string resault[][]=new string[row+1][col+1]; for(int k=0;k<row;++k){ for(int t=0;t<col;++t){ resault[k][t]=(maze[k][t])+""; } } while (!newpos.empty()) { position p1=newpos.pop(); resault[p1.row-1][p1.col-1]="#"; } for(int k=0;k<row;++k){ for(int t=0;t<col;++t){ system.out.print(resault[k][t]+"\t"); } system.out.println(); } } int maze[][]; private int row = 9; private int col = 8; stack<position> stack; boolean p[][] = null;}class hello{ public static void main(string[] args){ maze demo = new maze(); demo.init(); demo.findpath(); }} |
運行示例：
請輸入迷宮的行數(shù)
3
請輸入迷宮的列數(shù)
3
請輸入3行3列的迷宮
0 1 1
0 0 1
1 0 0
有路徑
路徑如下：
請輸入迷宮的行數(shù)
9
請輸入迷宮的列數(shù)
8
請輸入9行8列的迷宮
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 1 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
有路徑
路徑如下：
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://blog.csdn.net/u013474436/article/details/47977867
