个人博客
0%

NYOJ58-广度优先搜索算法

发表于 分类于

NYOJ-58-广度优先搜索算法

最近三天学习了深度优先算法，并做了一道oj题，遇到了一些问题，并解决了一些问题，这里记录一下。

题目描述：

描述

这有一个迷宫，有0~8行和0~8列：

1,1,1,1,1,1,1,1,1
1,0,0,1,0,0,1,0,1
1,0,0,1,1,0,0,0,1
1,0,1,0,1,1,0,1,1
1,0,0,0,0,1,0,0,1
1,1,0,1,0,1,0,0,1
1,1,0,1,0,1,0,0,1
1,1,0,1,0,0,0,0,1
1,1,1,1,1,1,1,1,1

0表示道路，1表示墙。
现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？
（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）

输入描述

第一行输入一个整数n（0<n<=100），表示有n组测试数据;
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。

输出描述

输出最少走几步。

解题源码

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
import java.util.*;

public class OJ58 {
    static int[][] walked =new int[9][9]; //记录那些路径走过
    static Queue<location> queue = new LinkedList<location>();//创建队列，将所有的位置都走一遍


    static int[][] map={{1,1,1,1,1,1,1,1,1},
            {1,0,0,1,0,0,1,0,1},
            {1,0,0,1,1,0,0,0,1},
            {1,0,1,0,1,1,0,1,1},
            {1,0,0,0,0,1,0,0,1},
            {1,1,0,1,0,1,0,0,1},
            {1,1,0,1,0,1,0,0,1},
            {1,1,0,1,0,0,0,0,1},
            {1,1,1,1,1,1,1,1,1}};

    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            int d = in.nextInt();

            if (a == c && b == d) {
                System.out.println(0);
                continue;
            }
            move(a, b,0);
            while (queue.size() != 0) {
                location laca = queue.poll();
//                System.out.print("走过(");
//                System.out.print(laca.x);
//                System.out.print(",");
//                System.out.print(laca.y);
//                System.out.print(")位置");
//                System.out.print("，步数");
//                System.out.println(laca.step);

                if (laca.x == c && laca.y == d) {
                    System.out.println(laca.step);
                    queue.clear();
                    for (int w = 0; w < 9; w++) {
                        Arrays.fill(walked[w], 0);//二维数组全部赋值为0
                    }

                    break;
                } else {
                    move(laca.x,laca.y, laca.step);
                }
            }
        }
    }


    private static void move(int x, int y, int steps) { //每个点上下左右移动

        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(-1);
        for (int i : list) {
            if (x + i > -1 && x + i <= 8 && walked[x + i][y] == 0 && map[x + i][y] == 0) {
                walked[x + i][y] = 1;
                location laca = new location();
                laca.x = x + i;
                laca.y = y;
                laca.step =steps+1;
                queue.offer(laca);
            }
        }
        for (int i : list) {
            if (y + i > -1 && y + i <= 8 && walked[x][y + i] == 0 && map[x][y + i] == 0) {
                walked[x][y + i] = 1;
                location laca = new location();
                laca.x = x;
                laca.y = y+i;
                laca.step = steps+1;
                queue.offer(laca);
            }
        }
    }



}

class location {
    int x;
    int y;
    int step;
}

遇到的问题

java结构体

java没有结构体，Queue E是泛型 可以自己构建类去充当元素，使用object =null去释放赋值对象。

1
2
3
4
5
6
7
8
9
//Interface Queue<E>
class location {
    int x;
    int y;
    int step;
}

location laca = new location();
queue.offer(laca);

多维数组赋值为0

java.util.Arrays.fill()方法处理的是一维数组，处理二维数组使用：

1
2
3
for (int w = 0; w < 9; w++) {
    Arrays.fill(walked[w], 0);//二维数组全部赋值为0
}

心得

广度优先搜索可以解决最短路径问题，像火一样蔓延，一层层去查找。