蓝桥杯算法提高VIP-密码锁 （C++代码）

解题思路:

        BFS + Hash。Hash 用来记录某个状态是否走过。广搜每次都与相邻位置交换入列即可。

参考代码:

#include<bits/stdc++.h>
using namespace std;
 
int Len;
bool Vis[31309];
typedef struct {
	string Pass; int Step;
} status;
queue<status> que;

bool find(string Pass) {
	if (Pass.find("2012") == string::npos)
		return false;
	return true;
}

int Hash(string Pass) {
	int hash = 0;
	for (int i = 0; i < Len; i++)
		hash += hash * 2 + Pass[i] - 41;
	return hash % 29231;
}

int BFS() {
	while (!que.empty()) {
		status now = que.front(); que.pop();
		for (int pos = 0; pos < Len - 1; pos++) {
			swap(now.Pass[pos], now.Pass[pos + 1]); 
			now.Step++;

			if (find(now.Pass))
				return now.Step;
			int hashValue = Hash(now.Pass);
			if (!Vis[hashValue]) {
				Vis[hashValue] = true; que.push(now);
			}
			now.Step--;
			swap(now.Pass[pos], now.Pass[pos + 1]);
		}
	}
	return -1;
}

int main() {
	status start; start.Step = 0;
	cin >> Len >> start.Pass;
	if (start.Pass.find("2012") == string::npos) {
		que.push(start); cout << BFS();
	}
	else cout << 0;
}