GuilinDev

Lc0752

05 August 2008

752 Open the Lock

圆形转盘锁解锁 - BFS

原题

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: 

1

'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
. The wheels can rotate freely and wrap around: for example we can turn 
1

'9'
to be 
1

'0'
, or 
1

'0'
to be 
1

'9'
. Each move consists of turning one wheel one slot.

The lock initially starts at 

1

'0000'
, a string representing the state of the 4 wheels.

You are given a list of 

1

deadends
dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a 

1

target
representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1:

1
2
3
4
5
6

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

1
2
3
4

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

1
2
3
4

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.

Example 4:

1
2

Input: deadends = ["0000"], target = "8888"
Output: -1

Constraints:

  • 1

    1 <= deadends.length <= 500

  • 1

    deadends[i].length == 4

  • 1

    target.length == 4
  • target will not be in the list 
    1

    deadends
    .
  • 1

    target
    and 
    1

    deadends[i]
    consist of digits only.

思路

BFS，类似111-求二叉树的最小深度。

BFS可以求解最值问题，当每种密码锁每次都转动一次时，总共有8个相邻的密码值，当这8个中有target值时，步数+1并返回，可以理解为树的结构，每个结点都有8个子结点，当从子结点中找到target时，步数+1并返回。所以可以用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

class Solution {
    public int openLock(String[] deadends, String target) {
        //当前处理的转盘字符
        Queue<String> queue = new LinkedList<>();
        //死亡转盘字符
        Set<String> deads = new HashSet<>();
        //字符被访问过的列表
        Set<String> visited = new HashSet<>();
        Collections.addAll(deads, deadends);
        //单个源点触发
        queue.offer("0000");
        visited.add("0000");
        int distance = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();
                //跳过死亡转盘字符
                if (deads.contains(curr)) continue;
                //找到了
                if (target.equals(curr)) {
                    return distance;
                }
                //四个数每个位置两种选择up down 4*2 =8 种
                for (int j = 0; j < 4; j++) {
                    String up = getUp(curr, j);
                    //要没被访问过的
                    if (!visited.contains(up)) {
                        queue.offer(up);
                        visited.add(up);
                    }
                    String down = getDown(curr, j);
                    if (!visited.contains(down)) {
                        queue.offer(down);
                        visited.add(down);
                    }
                }
            }
            //层数+1，当前层结束
            distance++;
        }
        return -1;
    }

    /**
     * 生成当前字符往上递增的字符 如 9000-->1000  2000->3000
     *
     * @param base
     * @param idx
     * @return
     */
    private String getUp(String base, int idx) {
        char[] chas = base.toCharArray();
        if (chas[idx] == '9') chas[idx] = '0';
        else chas[idx]++;
        return String.valueOf(chas);
    }

    /**
     * 生成当前字符往下递增的字符 如 9000-->8000  1000->9000
     *
     * @param base
     * @param index
     * @return
     */
    private String getDown(String base, int index) {
        char[] chas = base.toCharArray();
        if (chas[index] == '0') chas[index] = '9';
        else chas[index]--;
        return String.valueOf(chas);
    }
}
This site is open source. Improve this page.