# 752. 打开转盘锁

<https://leetcode-cn.com/problems/open-the-lock/>

## 解法一：bfs

起点是字符串"0000"，终点是target，求"0000"变为target的最少操作次数，即bfs问题

```python
import queue
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        q = queue.Queue()   #队列
        q.put('0000')   #初始放入起点
        visited = set()  #记录访问过的结点
        deadendsSet = set(deadends)     #deadends转为集合加快查询
        step = 0  #旋转次数
        visited.add("0000")   #标记起点已访问
        
        #辅助函数
        #将s[j]位加1
        def plusOne(s, j):
            chs = list(s)
            if chs[j] == '9':
                chs[j] = '0'
            else:
                chs[j] = str(int(chs[j])+1)
            return ''.join(chs)
        #将s[j]位减1
        def minusOne(s, j):
            chs = list(s)
            if chs[j] == '0':
                chs[j] = '9'
            else:
                chs[j] = str(int(chs[j])-1)
            return ''.join(chs)
        
        
        while not q.empty():
            #记录当前队列大小（BFS本轮迭代），以供后续遍历
            size = q.qsize()
            for i in range(size):                
                cur = q.get()  #从队列取出一个
                if cur in deadendsSet:
                    continue
                if cur == target:
                    return step
                for j in range(4):
                    #cur[j]加一，结果放入队列
                    p = plusOne(cur, j)
                    if p not in visited:
                        q.put(p)
                        visited.add(p)
                    #cur[j]减一，结果放入队列
                    m = minusOne(cur, j)
                    if m not in visited:
                        q.put(m)
                        visited.add(m)
            step += 1
        return -1
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cai-sen-se.gitbook.io/leetcode/601-800/752.-da-kai-zhuan-pan-suo.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.