算法笔记之图论

打开转盘锁

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

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

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

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

这个问题是一个典型的搜索问题，可以使用广度优先搜索（BFS）来解决。每一步都是通过旋转拨轮产生新的锁状态，然后判断是否到达目标状态。在搜索过程中，需要避开死亡数字（deadends）。

class Solution {
public:
	int openLock(vector<string>& deadends, string target) {
		unordered_set<string> deadSet(deadends.begin(), deadends.end());
		unordered_set<string> visited;

		queue<string> q;
		q.push("0000");
		visited.insert("0000");

		int steps = 0;

		while (!q.empty()) {
			int size = q.size();
			for (int i = 0; i < size; ++i) {
				string current = q.front();
				q.pop();

				if (current == target) {
					return steps;
				}

				if (deadSet.find(current) != deadSet.end()) {
					continue;
				}

				// 生成新的状态
				for (int j = 0; j < 4; ++j) {
					for (int k = -1; k <= 1; k += 2) {
						string next = current;
						next[j] = (next[j] - '0' + k + 10) % 10 + '0';

						if (visited.find(next) == visited.end()) {
							q.push(next);
							visited.insert(next);
						}
					}
				}
			}

			++steps;
		}

		return -1; // 无法解锁
	}
};