AcWing 181. 回转游戏(STL思想+暴力优化)

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 181. 回转游戏(STL思想+暴力优化) 原题链接中等

作者：

greenhand.n , 2022-08-11 16:12:08 , 所有人可见 , 阅读 240

2

1

题目描述

如下图所示，有一个 # 形的棋盘，上面有 1,2,3 三种数字各 8 个。

给定 8 种操作，分别为图中的 A∼H。

这些操作会按照图中字母和箭头所指明的方向，把一条长为 7 的序列循环移动 1 个单位。

例如下图最左边的 # 形棋盘执行操作 A 后，会变为下图中间的 # 形棋盘，再执行操作 C 后会变成下图最右边的 # 形棋盘。

给定一个初始状态，请使用最少的操作次数，使 # 形棋盘最中间的 8 个格子里的数字相同。

2286_1.jpg

输入格式
输入包含多组测试用例。

每个测试用例占一行，包含 24 个数字，表示将初始棋盘中的每一个位置的数字，按整体从上到下，同行从左到右的顺序依次列出。

输入样例中的第一个测试用例，对应上图最左边棋盘的初始状态。

当输入只包含一个 0 的行时，表示输入终止。

输出格式
每个测试用例输出占两行。

第一行包含所有移动步骤，每步移动用大写字母 A∼H 中的一个表示，字母之间没有空格，如果不需要移动则输出 No moves needed。

第二行包含一个整数，表示移动完成后，中间 8 个格子里的数字。

如果有多种方案，则输出字典序最小的解决方案。

样例

1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
0
blablabla
AC
2
DDHH
2

STL大法+IDA*（赶时间的话可以看代码末尾）

用四个deque维护四个长条，A是将队首放入队尾，F则相反
读入时需一点点暴力。
DFS时check一下8个方块里最多的数字是多少，用8减去它，得到估价，若估价+当前步数>限制深度则return.可以在搜索树找到最浅处的答案。
复杂度O(7^k)* $\omega$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4 * 1e5 + 10, mod = 1e9 + 7;// mod = 1949777;
int a[maxn];
deque<int> dq[5];
int s[30];
int maxdep, flag = 0, num_ans;
deque<char> ans, t;
int num[5];
int check() {
    return max(num[1], max(num[2], num[3]));
}
int opposite[8] = {5, 4, 7, 6, 1, 0, 3, 2};
int mp[8] = {1, 2, 3, 4, 2, 1, 4, 3};
void dfs(int now, int lst) {
    if (flag) return;
    int res = check();
    if (res == 8) {
        num_ans = dq[1][2];
        if (maxdep) for(auto i: ans) cout << i;
        else cout << "No moves needed";
        cout << endl << num_ans << endl;
        flag = 1;
        return;
    }
    if (8 - res + now > maxdep) return;
    for (int i = 0; i < 8; i++) {
        if (lst == opposite[i]) continue;
        ans.push_back((char)(i + 'A'));
        int id = mp[i];
        if (i < 4) {
            num[dq[id][2]]--; num[dq[id][5]]++; 
            dq[id].push_back(dq[id].front()), dq[id].pop_front();
        }
        else {
            num[dq[id][4]]--; num[dq[id][1]]++; 
            dq[id].push_front(dq[id].back()), dq[id].pop_back();
        }
        if (id <= 2) {
                dq[3][4] = dq[1][2];
                dq[3][2] = dq[2][2];
                dq[4][4] = dq[1][4];
                dq[4][2] = dq[2][4];
            } else {
                dq[1][2] = dq[3][4];
                dq[2][2] = dq[3][2];
                dq[1][4] = dq[4][4];
                dq[2][4] = dq[4][2];
        }
        dfs(now + 1, i);
        if (i < 4) {
            num[dq[id][4]]--; num[dq[id][1]]++; 
            dq[id].push_front(dq[id].back()), dq[id].pop_back();
        }
        else {
            num[dq[id][2]]--; num[dq[id][5]]++; 
            dq[id].push_back(dq[id].front()), dq[id].pop_front();
        }
        if (id <= 2) {
            dq[3][4] = dq[1][2];
            dq[3][2] = dq[2][2];
            dq[4][4] = dq[1][4];
            dq[4][2] = dq[2][4];
            } else {
            dq[1][2] = dq[3][4];
            dq[2][2] = dq[3][2];
            dq[1][4] = dq[4][4];
            dq[2][4] = dq[4][2];
        }
        ans.pop_back();
    }
}
void solve() {
    flag = 0;
    for (int i = 1; i <= 4; i++) dq[i].clear(); ans.clear();
    for (int i = 1; i <= 3; i++) num[i] = 0;
    int cnt = 0;
    for (int i = 0; i < 24; i++) {
        cnt++; 
        if (5 <= cnt && cnt <= 5 + 7 - 1) dq[3].push_front(s[i]);
        else if (14 <= cnt && cnt <= 14 + 7 - 1) dq[4].push_front(s[i]);
        if (cnt == 1 || cnt == 3 || cnt == 7 || cnt == 12 || cnt == 16 || cnt == 21 || cnt == 23) dq[1].push_back(s[i]);
        else if (cnt == 2 || cnt == 4 || cnt == 9 || cnt == 13 || cnt == 18 || cnt == 22 || cnt == 24) dq[2].push_back(s[i]); 
    }
    for (int i = 1; i <= 2; i++) {
        num[dq[i][2]]++;
        num[dq[i][3]]++;
        num[dq[i][4]]++;
    }
    num[dq[3][3]]++; num[dq[4][3]]++;
    maxdep = 8 - check();
    while(1) {
        dfs(0, -1);
        if (flag) break;
        maxdep++;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(1) {
        for (int i = 0; i < 24; i++) {
            cin >> s[i];
            if (s[0] == 0) return 0;
        } 
        solve();
    } 
    return 0;
}

然后你惊奇地发现你这样会TLE，什么！！居然是常数太大了，%%%#*###**！

优化：

手动模拟deque,由于每个最多有7个，所以直接模拟比常数还小
时间复杂度O(7^k)

C++ 代码

#include <bits/stdc++.h>
#define for_(i,a,b) for (ll i = (a); i < (b); i++)
#define rep_(i,a,b) for (ll i = (a); i <= (b); i++)
#define fi first 
#define se second
using namespace std;
const int maxn = 4 * 1e5 + 10, mod = 1e9 + 7;// mod = 1949777;
int n, m;
int dq[5][8];
int s[30];
int maxdep, flag = 0, num_ans;
int ans[maxn];
int num[5];
int check() {
    return max(num[1], max(num[2], num[3]));
}
int opposite[8] = {5, 4, 7, 6, 1, 0, 3, 2};
int mp[8] = {1, 2, 3, 4, 2, 1, 4, 3};
int cnt = 0;
int c[5];
void make(int tmp[8], int k) {
    if (k == 1) {
        int x = tmp[0];
        for (int i = 0; i <= 5; i++) tmp[i] = tmp[i + 1];
        tmp[6] = x;
    } else {
        int x = tmp[6];
        for (int i = 6; i >= 1; i--) tmp[i] = tmp[i - 1];
        tmp[0] = x;
    } 
    return;
}
void dfs(int now, int lst) {
    if (flag) return;
    int res = check();
    if (res == 8) {
        num_ans = dq[1][2];
        if (maxdep) for(int i = 1; i <= cnt; i++) printf("%c", (ans[i] + 'A'));
        else printf("No moves needed");
        printf("\n%d\n", num_ans); 
        flag = 1;
        return;
    }
    if (8 - res + now > maxdep) return;
    for (int i = 0; i < 8; i++) {
        if (flag) return;
        if (lst == opposite[i]) continue;
        ans[++cnt] = i;
        int id = mp[i];
        if (i < 4) {
            num[dq[id][2]]--; num[dq[id][5]]++; 
//          dq[id].push_back(dq[id].front()), dq[id].pop_front();
            make(dq[id], 1);
        }
        else {
            num[dq[id][4]]--; num[dq[id][1]]++; 
//          dq[id].push_front(dq[id].back()), dq[id].pop_back();
            make(dq[id], -1);
        }
        if (id <= 2) {
                dq[3][4] = dq[1][2];
                dq[3][2] = dq[2][2];
                dq[4][4] = dq[1][4];
                dq[4][2] = dq[2][4];
            } else {
                dq[1][2] = dq[3][4];
                dq[2][2] = dq[3][2];
                dq[1][4] = dq[4][4];
                dq[2][4] = dq[4][2];
        }
        dfs(now + 1, i);
        if (i < 4) {
            num[dq[id][4]]--; num[dq[id][1]]++; 
//          dq[id].push_front(dq[id].back()), dq[id].pop_back();
            make(dq[id], -1);
        }
        else {
            num[dq[id][2]]--; num[dq[id][5]]++; 
//          dq[id].push_back(dq[id].front()), dq[id].pop_front();
            make(dq[id], 1);
        }
        if (id <= 2) {
            dq[3][4] = dq[1][2];
            dq[3][2] = dq[2][2];
            dq[4][4] = dq[1][4];
            dq[4][2] = dq[2][4];
            } else {
            dq[1][2] = dq[3][4];
            dq[2][2] = dq[3][2];
            dq[1][4] = dq[4][4];
            dq[2][4] = dq[4][2];
        }
        cnt--;
    }
}
void solve() {
    flag = 0;
    c[1] = c[2] = 0;
    c[3] = c[4] = 6;
    for (int i = 1; i <= 3; i++) num[i] = 0;
    cnt = 0;
    for (int i = 0; i < 24; i++) {
        cnt++; 
        if (5 <= cnt && cnt <= 5 + 7 - 1) dq[3][c[3]--] = s[i];
        else if (14 <= cnt && cnt <= 14 + 7 - 1) dq[4][c[4]--] = s[i];
        if (cnt == 1 || cnt == 3 || cnt == 7 || cnt == 12 || cnt == 16 || cnt == 21 || cnt == 23) dq[1][c[1]++] = s[i];
        else if (cnt == 2 || cnt == 4 || cnt == 9 || cnt == 13 || cnt == 18 || cnt == 22 || cnt == 24) dq[2][c[2]++] = s[i]; 
    }
    cnt = 0;
    for (int i = 1; i <= 2; i++) {
        num[dq[i][2]]++;
        num[dq[i][3]]++;
        num[dq[i][4]]++;
    }
    num[dq[3][3]]++; num[dq[4][3]]++;
    maxdep = 8 - check();
    while(1) {
        dfs(0, -1);
        if (flag) break;
        maxdep++;
    }
}
signed main() {
    while(1) {
        for (int i = 0; i < 24; i++) {
            scanf("%d", &s[i]);
            if (s[0] == 0) return 0;
        } 
        solve();
    } 
    return 0;
} 
//2022年8月11日16:11:54 By CR