解题思路:
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; }
0.0分
5 人评分