藍橋杯 最短路徑問題

試題描述：最短路徑問題。

定義一個二維數組：

int maze = {

{0, 1, 0, 0, 0},

{0, 1, 0, 1, 0},

{0, 0, 0, 0, 0},

{0, 1, 1, 1, 0},

{0, 0, 0, 1, 0}

};

它表示一個迷宮，其中的1表示牆壁，0表示可以走的路，只能橫著走或豎著走，不能斜著走，要求編程序找出從左上角到右下角的最短路線。

輸出的效果是

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

請將以下代碼補充完整。

1 import java.util.*;
2
3 public class Main{
4 private class Point {
5 int x = 0;
6 int y = 0;
7
8 public Point {
9 this(0, 0);
10 }
11
12 public Point(int x, int y) {
13 this.x = x;
14 this.y = y;
15 }
16
17 public boolean equals(Point p) {
18 return (this.x == p.x) && (this.y == p.y); // 填入第1行代碼 完成點與點的比較
19 }
20
21 public String toString {
22 return "(" + x + ", " + y + ")";
23 }
24 }
25
26 private int maze = null;
27 private Stack stack = new Stack;
28
29 public Main(int[][] maze) {
30 this.maze = maze;
31 }
32
33 public void go {
34 Point out = new Point(maze.length - 1, maze[0].length - 1);
35 Point in = new Point(0, 0);
36 Point curNode = in;
37 Point nextNode = null;
38 while (!curNode.equals(out)) {
39
40 nextNode = new Point(curNode.x, curNode.y);
41
42 if ((nextNode.x+1=0)&&(maze[curNode.x-1][curNode.y] == 0)) { // 填入第4行代碼
47 nextNode.x--;
48 } else if ((nextNode.y-1>=0)&&(maze[curNode.x][curNode.y-1] == 0)) { // 填入第5行代碼
49 nextNode.y--;
50 } else {
51 maze[curNode.x][curNode.y] = 3;
52 if (stack.isEmpty) {
53 System.out.println("Non solution");
54 return;
55 }
56 curNode = stack.pop;
57 continue;
58 }
59 stack.push(curNode);
60 maze[curNode.x][curNode.y] = 2;
61 curNode = nextNode;
62 }
63
64 if (nextNode.equals(out)) {
65 stack.push(nextNode);
66 maze[nextNode.x][nextNode.y] = 2;
67 }
68 for (int i = 0; i < stack.size; i++) 69 System.out.println(stack.elementAt(i)); 70 } 71 72 public static void main(String[] args) { 73 int maze = { { 0, 1, 0, 0, 0 }, { 0, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 0 }, 74 { 0, 0, 0, 1, 0 } }; 75 new Main(maze).go; 76 } 77 }

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！