RT

虽然水过了这一题

但是双向宽搜跑的比单项宽搜快？

（刚刚太SB，标题写反，导致很多大佬误解，现重开一贴，看过的大佬可以忽略）

附单项宽搜代码（300+ms）：

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int s[6][6];
    int step = 0;
};
Node n;
Node ans;
Node q[66666];
int h[66666];
int POWER(int x, int s) {
    for (int i = s; i >= 1; i--) {
        x *= 2;
    }
    return x;
}
int CHANGE(Node x) {
    int k = 15;
    int ans = 0;
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            ans += POWER(x.s[i][j], k);
            k--;
        }
    }
    return ans;
}
int rear = 0;
int front = 1;
void PUSH(Node s) {
    q[++rear] = s;
    h[CHANGE(s)]++;
}
bool CHECK_ANS(Node x) {
    if (CHANGE(x) == CHANGE(ans)) {
        return true;
    } else {
        return false;
    }
}
bool CHECK(Node x) {
    if (h[CHANGE(x)] == -1) {
        return true;
    } else {
        return false;
    }
}
Node GO1(Node s, int x, int y) {
    if (x + 1 <= 4) {
        Node ans;
        if (s.s[x][y] == s.s[x + 1][y]) {
            return s;
        } else {
            ans.step = s.step + 1;
            for (int i = 1; i <= 4; i++) {
                for (int j = 1; j <= 4; j++) {
                    ans.s[i][j] = s.s[i][j];
                }
            }
            swap(ans.s[x][y], ans.s[x + 1][y]);
            return ans;
        }
    }
}
Node GO2(Node s, int x, int y) {
    if (y + 1 <= 4) {
        Node ans;
        if (s.s[x][y] == s.s[x][y + 1]) {
            return s;
        } else {
            ans.step = s.step + 1;
            for (int i = 1; i <= 4; i++) {
                for (int j = 1; j <= 4; j++) {
                    ans.s[i][j] = s.s[i][j];
                }
            }
            swap(ans.s[x][y], ans.s[x][y + 1]);
            return ans;
        }
    }
}
void BFS() {
    Node p;
    Node s1;
    Node s2;
    while (front <= rear) {
        p = q[front];
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                if (i != 4) {
                    s1 = GO1(p, i, j);
                    if (CHECK_ANS(s1)) {
                        cout << s1.step << endl;
                        return;
                    }
                    if (CHECK(s1)) {
                        PUSH(s1);
                    }
                }
                if (j != 4) {
                    s2 = GO2(p, i, j);
                    if (CHECK_ANS(s2)) {
                        cout << s2.step << endl;
                        return;
                    }
                    if (CHECK(s2)) {
                        PUSH(s2);
                    }
                }
            }
        }
        front++;
    }
    return;
}
int main() {
    memset(h, -1, sizeof(h));
    char ch[22];
    char ch1[22];
    char ch2[22];
    for (int i = 1; i <= 4; i++) {
        gets(ch1);
        int p = 0;
        for (int j = 1; j <= 4; j++) {
            n.s[i][j] = ch1[p] - '0';
            p++;
        }
    }
    gets(ch);
    n.step = 0;
    for (int i = 1; i <= 4; i++) {
        gets(ch2);
        int p = 0;
        for (int j = 1; j <= 4; j++) {
            ans.s[i][j] = ch2[p] - '0';
            p++;
        }
    }
    PUSH(n);
    if (CHECK_ANS(n)) {
        cout << 0 << endl;
        return 0;
    }
    BFS();
    return 0;
}

附双向宽搜代码（2000+ms）：

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int s[6][6];

    int step = 0;
};
struct Hash {
    int h = 0;

    int step = 0;
};
Node n;
Node ans;
queue<Node> q1;
queue<Node> q2;
int POWER(int x, int s) {
    for (int i = s; i >= 1; i--) {
        x *= 2;
    }
    return x;
}
Hash h1[66666];
Hash h2[66666];
int CHANGE(Node x) {
    int k = 15;
    int ans = 0;
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            ans += POWER(x.s[i][j], k);
            k--;
        }
    }
    return ans;
}
void PUSH(Node s, int x) {
    if (x == 1) {
        q1.push(s);
        h1[CHANGE(s)].h++;
        h1[CHANGE(s)].step = s.step;
        return;
    } else {
        q2.push(s);
        h2[CHANGE(s)].h++;
        h2[CHANGE(s)].step = s.step;
        return;
    }
    return;
}
int check = 0;
void CHECK_ANS() {
    for (int i = 1; i < 66666; i++) {
        if (h1[i].h == 0 && h2[i].h == 0) {
            cout << h1[i].step + h2[i].step << endl;
            check = 1;
            return;
        }
    }
}
bool CHECK(Node x, int s) {
    if (s == 1) {
        if (h1[CHANGE(x)].h == -1) {
            return true;
        } else {
            return false;
        }
    } else {
        if (h2[CHANGE(x)].h == -1) {
            return true;
        } else {
            return false;
        }
    }
}
Node GO1(Node s, int x, int y) {
    if (x + 1 <= 4) {
        Node ans;
        if (s.s[x][y] == s.s[x + 1][y]) {
            return s;
        } else {
            ans.step = s.step + 1;
            for (int i = 1; i <= 4; i++) {
                for (int j = 1; j <= 4; j++) {
                    ans.s[i][j] = s.s[i][j];
                }
            }
            swap(ans.s[x][y], ans.s[x + 1][y]);
            return ans;
        }
    }
}
Node GO2(Node s, int x, int y) {
    if (y + 1 <= 4) {
        Node ans;
        if (s.s[x][y] == s.s[x][y + 1]) {
            return s;
        } else {
            ans.step = s.step + 1;
            for (int i = 1; i <= 4; i++) {
                for (int j = 1; j <= 4; j++) {
                    ans.s[i][j] = s.s[i][j];
                }
            }
            swap(ans.s[x][y], ans.s[x][y + 1]);
            return ans;
        }
    }
}
Node GO3(Node s, int x, int y) {
    if (x - 1 >= 1) {
        Node ans;
        if (s.s[x][y] == s.s[x - 1][y]) {
            return s;
        } else {
            ans.step = s.step + 1;
            for (int i = 1; i <= 4; i++) {
                for (int j = 1; j <= 4; j++) {
                    ans.s[i][j] = s.s[i][j];
                }
            }
            swap(ans.s[x][y], ans.s[x - 1][y]);
            return ans;
        }
    }
}
Node GO4(Node s, int x, int y) {
    if (y - 1 >= 1) {
        Node ans;
        if (s.s[x][y] == s.s[x][y - 1]) {
            return s;
        } else {
            ans.step = s.step + 1;
            for (int i = 1; i <= 4; i++) {
                for (int j = 1; j <= 4; j++) {
                    ans.s[i][j] = s.s[i][j];
                }
            }
            swap(ans.s[x][y], ans.s[x][y - 1]);
            return ans;
        }
    }
}
void BFS() {
    Node p;
    Node s1;
    Node s2;
    int flag = 0;
    while (!q1.empty() && !q2.empty()) {
        if (flag != 2) {
            p = q1.front();
        }
        for (int i = 1; i <= 4; i++) {
            if (flag == 2) {
                break;
            }
            for (int j = 1; j <= 4; j++) {
                if (i != 4) {
                    s1 = GO1(p, i, j);
                    if (CHECK(s1, 1)) {
                        PUSH(s1, 1);
                    }
                }
                if (j != 4) {
                    s2 = GO2(p, i, j);
                    if (CHECK(s2, 1)) {
                        PUSH(s2, 1);
                    }
                }
            }
        }
        CHECK_ANS();
        if (check == 1) {
            return;
        }
        if (flag != 2) {
            q1.pop();
        }
        if (q1.size() < q2.size()) {
            flag = 1;
        } else {
            flag = 2;
        }
        if (flag != 1) {
            p = q2.front();
        }
        for (int i = 4; i >= 1; i--) {
            if (flag == 1) {
                break;
            }
            for (int j = 4; j >= 1; j--) {
                if (i != 1) {
                    s1 = GO3(p, i, j);
                    if (CHECK(s1, 2)) {
                        PUSH(s1, 2);
                    }
                }
                if (j != 1) {
                    s2 = GO4(p, i, j);
                    if (CHECK(s2, 2)) {
                        PUSH(s2, 2);
                    }
                }
            }
        }
        CHECK_ANS();
        if (check == 1) {
            return;
        }
        if (flag != 1) {
            q2.pop();
        }
        if (q1.size() < q2.size()) {
            flag = 1;
        } else {
            flag = 2;
        }
    }
    return;
}
int main() {
    memset(h1, -1, sizeof(h1));
    memset(h2, -1, sizeof(h2));
    char ch[22];
    char ch1[22];
    char ch2[22];
    for (int i = 1; i <= 4; i++) {
        gets(ch1);
        int p = 0;
        for (int j = 1; j <= 4; j++) {
            n.s[i][j] = ch1[p] - '0';
            p++;
        }
    }
    gets(ch);
    PUSH(n, 1);
    n.step = 0;
    for (int i = 1; i <= 4; i++) {
        gets(ch2);
        int p = 0;
        for (int j = 1; j <= 4; j++) {
            ans.s[i][j] = ch2[p] - '0';
            p++;
        }
    }
    PUSH(ans, 2);
    ans.step = 0;
    CHECK_ANS();
    if (check == 1) {
        return 0;
    }
    BFS();
    return 0;
}

是不是我的HASH遍历太麻烦了？

还是其他玄学问题，求大佬指教

谢谢