BFS 打地鼠

字数统计1.2k阅读时长11分阅读次数

Whack-A-Mole

Problem

This time we’ll play a variation of Whack-A-Mole! We’ll play this game on a board with 16
holes, from which individual moles pop-up. Using a mallet you can then “whack a mole”
and make it go hide underground. As you might know, however, whacking a mole will
often have the effect of making other moles rise and come out from the ground. In this
version of the game, every time you hit a mole with the mallet you’ll cause the immediate
four adjacent holes to change: any moles currently there will hide, while new moles popup from previously empty holes.
Imagine, for example, that you find yourself in the following game configuration, and you
prepare yourself to hit the mole at position 10 with the mallet.

You will cause the moles in positons 9, 10, 11, and 14 to hide, but you’ll also make a mole
appear at position 6. Thus ending up in the next configuration.

If you then hit the mole at position 2, then all of the moles at positions 1, 2, and 6 will hide;
but a new one in position 3 will appear. There is no use of hitting empty holes, as nothing
in the board will change. You may assume that all puzzles have a solution.
Your task is to write a computer program which, given an initial board configuration, finds
ashortest sequence of moles that you can hit in order to empty the board.
There might be several correct solutions with the same optimal length, finding any of them
will be enough. Your answer should be given as a sequence of numbers with the correct
order of moles to “whack”, each separated by a single space.

Example
Find one of the shortest sequences of moles you have to hit in order to clear the board if
starting from the configuration with moles at positions 1, 2, 4, 8, 9, 10, 11, and 14.
Discussion: This is the same configuration of moles as given in the first illustration above.
After hitting moles at positions 10 and 2, you’ll end up in the following configuration.

At this point, a single hit to the mole at position 4 will clear the board.
Answer: 10 2 4
Attempts: 2 out of Infinity
Coursework uses your best attempt for grading.
Final marks: 9 / 9 (100.0%)

分析：

  1. 其实题目就是问我们怎么样敲地鼠才能使得全部地鼠都躲起来
  2. 注意有地鼠才能敲，敲完之后该位置和四周位置地鼠状态会相反（躲起来的地鼠会站起来，站起来的地鼠会躲起来）
  3. 直接记录4*4矩阵状态，然后一路BFS出结果
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
import java.util.HashSet;
import java.util.LinkedList;
class matrix {
    String path = "";// 存放每次所打的地鼠
    boolean ma[][] = new boolean[4][4];// 局部变量，4*4的矩阵
    boolean cmp(matrix b) {// 判断是否相同
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                if (this.ma[i][j] != b.ma[i][j])
                    return false;
        return true;
    }
}
public class Main {
    //枚举四个方向
    static int dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
    /**
     * 输入参数矩阵，求出结果，默认结果都能求得解，否则只需添加判断次数条件，超过则认为不能得出结果
     * @param a 参数矩阵
     */
    static void bfs(matrix a) {
        LinkedList<matrix> q = new LinkedList<>();//实现队列效果
        HashSet<matrix> st = new HashSet<>();//判断是否已经存在，存在则不再继续存储矩阵
        matrix des = new matrix();//目标矩阵
        q.addLast(a);//加入队列
        st.add(a);//加入集合
        int step = 0;//步数
        while (q.size() != 0) {
            int tmpSize = q.size();//每一层bfs的数量
            for (int len = 0; len < tmpSize; len++) {//枚举每一层
                matrix cur = q.getFirst();//从队列头取出
                q.removeFirst();
                if (des.cmp(cur)) {//如果找到目标矩阵，则输出
                    System.out.println("一共需要敲打地鼠的次数：" + step);
                    System.out.println("敲打地鼠的顺序为：" + cur.path);
                    return;
                }
                for (int i = 3; i >= 0; i--) {//从3开始倒序是题目要求
                    for (int j = 3; j >= 0; j--) {
                        if (cur.ma[i][j]) {//要有地鼠才能敲打
                            matrix tmpmatrix = new matrix();
                            tmpmatrix.path = cur.path + " " + (i * 4 + j + 1) + " ";//记录路径
                            // 克隆原先的矩阵，在进行修改时才不会影响原先矩阵
                            for (int k = 0; k < 4; k++) {
                                for (int z = 0; z < 4; z++) {
                                    tmpmatrix.ma[k][z] = cur.ma[k][z];
                                }
                            }
                            tmpmatrix.ma[i][j] = !cur.ma[i][j];//敲打后地鼠下去了
                            for (int ll = 0; ll < 4; ll++) {//敲打周围四个方向地鼠会变化
                                int dx = i + dir[ll][0];
                                int dy = j + dir[ll][1];
                                if (dx >= 0 && dx < 4 && dy >= 0 && dy < 4) {
                                    tmpmatrix.ma[dx][dy] = !cur.ma[dx][dy];//有则变无，无则变有
                                }
                            }
                            if (st.contains(tmpmatrix)) {//矩阵已经有，则不存，否则可能造成死循环
                                continue;
                            }
                            st.add(tmpmatrix);//添加到集合
                            q.addLast(tmpmatrix);//添加到队列
                        }
                    }
                }
            }
            step++;
        }
    }
    public static void main(String[] args) {
        matrix now = new matrix();
        // int[] test = { 7, 8, 10, 11, 14 };
        // int[] test = {2,3,4,7,9,11,12,13};
        // int[] test = {1,3,4,5,6,7,10,11,12,13,15,16};
        // int[] test = {1,3,7,8,9,13,14,16};
        int[] test = {1,2,3,4,8,10,11,12};
        for (int x : test) {
            if (x % 4 != 0)//可有坐标推导
                now.ma[x / 4][x % 4 - 1] = true;
            else //如果是最右边的一列
                now.ma[x / 4 - 1][3] = true;
        }
        bfs(now);//bfs搜索结果
    }
}

优化： 由于只用了十六个数，所以其实可以用二进制进行压缩