手写字符串hash,参考题目: AcWing 841. 字符串哈希
手写 hash
#include <iostream>
#include <string>
#include <queue>
using namespace std;
const int N = 1000011, P = 131;
typedef unsigned long long ULL;
ULL h[11];
int d[N];
int hashing(string &a) {
h[0] = 0;
for (int i = 1; i <= 10; ++i)
h[i] = h[i - 1] * P + (a[i - 1] - '0');
return h[10] % N;
}
int bfs(string start) {
string end = "12345678x";
queue<string> q;
d[hashing(start)] = 0;
q.push(start);
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while (!q.empty()){
auto t = q.front(); q.pop();
int distance = d[hashing(t)];
if (t == end) return distance;
int k = t.find('x');
for (int i = 0; i < 4; ++i) {
int x = k / 3, y = k % 3;
x += dx[i], y += dy[i];
if (x >= 0 && x < 3 && y >= 0 && y < 3) {
swap(t[k], t[x * 3 + y]);
if (!d[hashing(t)]) {
d[hashing(t)] = distance + 1;
q.push(t);
}
swap(t[k], t[x * 3 + y]);
}
}
}
return -1;
}
int main() {
int n = 9;
string start;
while (n--) {
char c;
cin >> c;
start += c;
}
cout << bfs(start) << endl;
return 0;
}
手写hash和queue
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000011, P = 131;
typedef unsigned long long ULL;
ULL h[11];
int d[N]; // 距离
char q[362880 + 1000][10]; // 模拟队列, 每个单元是一个char [10], 9! = 362800
int hashing(char a[]) {
h[0] = 0;
for (int i = 1; i <= 10; ++i)
h[i] = h[i - 1] * P + (a[i - 1] - '0');
return h[10] % N;
}
int bfs(char start[]) {
char end[10] = "12345678x";
int hh = 0, tt = 0;
d[hashing(start)] = 0;
strcpy(q[0], start);
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
char t[10];
while (hh <= tt){
strcpy(t, q[hh++]);
int distance = d[hashing(t)];
if (!strcmp(t, end)) return distance;
int k = -1;
for (int i = 0; i < 10; ++i) if (t[i] == 'x') { k = i; break; }
int x = k / 3, y = k % 3;
for (int i = 0; i < 4; ++i) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 3 && b >= 0 && b < 3) {
swap(t[k], t[a * 3 + b]);
if (!d[hashing(t)]) {
d[hashing(t)] = distance + 1;
strcpy(q[++tt], t);
}
swap(t[k], t[a * 3 + b]);
}
}
}
return -1;
}
int main() {
char start[10];
for (int i = 0; i < 9; ++i) cin >> start[i];
start[9] = '\0';
cout << bfs(start) << endl;
return 0;
}
楼主请问一下队列数组要开到多大是怎么判断的呀
我也不知道,队列里到底入队了几次我不会判断。但一个行之有效的方法是在不超过题目内存限制的情况下尽可能的多开。害怕溢出的话还是用stl吧。stl的queue挺快的。
感谢评论!,刚刚思考了一下,因为字符串的每一个排列(如:“123456789x”,“12345678x9”)对应一个状态,每个状态对应图中的一个点。所以说整张图中所有点最多有9的全排列个,也就是图中点至多有9! = 362880个。又因为bfs算法中图每个点至多只遍历一次(也就是入队一次),所以说queue数组开到9!大小就够了。
啊哈有道理谢谢楼主