算法竞赛进阶指南-0x02-费解的开关

本文主要是介绍算法竞赛进阶指南-0x02-费解的开关，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

http://noi-test.zzstep.com/contest/0x00%E3%80%8C%E5%9F%BA%E6%9C%AC%E7%AE%97%E6%B3%95%E3%80%8D%E4%BE%8B%E9%A2%98/0201%20%E8%B4%B9%E8%A7%A3%E7%9A%84%E5%BC%80%E5%85%B3

因为这题是第一题（其实不是第一题），以为比较简单，一眼暴力，25⁶。算的时候少算了一位，以为规模是1e7，导致样例都算很慢，慢到我以为是死循环。找了半天死循环才发现这个代码其实能出结果...

然后就按照普通的翻转问题一行一行处理。代码恶臭，而且有一处变量名写错查了半个多小时。下面标出错误的地方

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
struct nd
{
    int a[6][6], sum;
} node[10000005];
int a[6][6], tot, ax[6][6];
const int oprx[] = {0, 0, 0, 1, -1}, opry[] = {0, 1, -1, 0, 0};
void gn(int sum)
{
    int i, j;
    for (i = 1; i <= 2; i++)
        for (j = 1; j < 6; j++)
            node[tot].a[i][j] = ax[i][j];
    node[tot].sum = sum;
    tot++;
    if (sum == 6)
        return;
    for (i = 1; i < 6; i++)
    {
        for (j = 0; j < 5; j++)
            ax[1 + oprx[j]][i + opry[j]] ^= 1;
        gn(sum + 1);
        for (j = 0; j < 5; j++)
            ax[1 + oprx[j]][i + opry[j]] ^= 1;
    }
}
inline int res(int x)
{
    int i, j;
    for (i = 1; i < 3; i++)
        for (j = 1; j < 6; j++)
            ax[i][j] = node[x].a[i][j];
    for (i = 3; i < 6; i++)
        for (j = 1; j < 6; j++)
            ax[i][j] = a[i][j];
    int ret = node[x].sum;
    for (i = 2; i < 6; i++)
    {
        for (j = 1; j < 6; j++)
        {
            if (!ax[i - 1][j])
            {
                for (int k = 0; k < 5; k++)
                    ax[i + oprx[k]][j + opry[k]] ^= 1; //这里的ax写成了a...离谱的是上面的if里面的ax原本也是没错的...
                ret++;
                if (ret > 6)
                    return -1;
            }
        }
    }
    for (i = 1; i < 6; i++)
    {
        if (!ax[5][i])
            return -1;
    }
    return ret;
}
int main()
{
    int _, i, j;
    scanf("%d", &_);
    while (_--)
    {
        for (i = 1; i <= 5; i++)
            for (j = 1; j <= 5; j++)
                scanf("%1d", &a[i][j]);
        for (i = 1; i < 3; i++)
            for (j = 1; j <= 5; j++)
                ax[i][j] = a[i][j];
        tot = 1;
        gn(0);
        int ans = -1;
        for (i = 1; i < tot; i++)
        {
            int t = res(i);
            if (t >= 0 && (ans > t || ans < 0))
                ans = t;
        }
        printf("%d\n", ans);
    }
    return 0;
}

后面队友提供了记忆化搜索的思路。大致是给矩阵的25个元素依次分一个位，形成一个二进制数，以这个二进制数作为存储中间结果的标识（状态）。

原本的思路是从0开始，求出每个标识到最终答案所需操作次数，超过六次的直接记非法。但队友指出，这样会造成大量不必要的计算，不如从最终答案开始，（用一个bfs）把所有从最终答案开始六步之内能到的状态标上。

有关状态的存取，原本想偷懒，每一次将状态展开为矩阵操作，操作完再转为状态。但还是那个队友，指出：相邻元素在状态中相差的位数是一定的，只需要判断边界值就可以。

然后就还算顺利地写出了代码。写完因为状态没及时转移，状态重复访问导致死循环。后面因为结构体中构造函数写错卡了半天，期间还在想是不是输入和输出的状态反了。经过推导，确实是反了，但因为矩阵是对称的，其实反不反对答案没有影响

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
int dp[1 << 25];
struct node
{
    int sta, sum;
    node(int s = 0, int su = 0)
    {
        sta = s;
        sum = su; //原本写成su=sum了
    }
};
void bfs()
{
    queue<node> q;
    int i, t;
    q.push(node((1 << 25) - 1, 0));
    while (!q.empty())
    {
        int sta = q.front().sta, sum = q.front().sum;
        q.pop();
        if (dp[sta] >= 0 && dp[sta] < sum)
            continue;
        dp[sta] = sum;
        if (sum > 5)
            continue;
        for (i = 0; i < 25; i++)
        {
            t = sta ^ (1 << i);
            if (i - 5 >= 0)
                t ^= (1 << (i - 5));
            if (i + 5 < 25)
                t ^= (1 << (i + 5));
            if (i % 5)
                t ^= (1 << (i - 1));
            if (i % 5 != 4)
                t ^= (1 << (i + 1));
            if (dp[t] < 0 || dp[t] > sum + 1)
            {
                dp[t] = sum + 1; //最开始没写这个导致死循环
                q.push(node(t, sum + 1));
            }
        }
    }
}
int main()
{
    int _, i, j, t, x;
    memset(dp, -1, sizeof(dp));
    bfs();
    scanf("%d", &_);
    while (_--)
    {
        x = 0;
        for (i = 1; i <= 5; i++)
        {
            for (j = 1; j <= 5; j++)
            {
                scanf("%1d", &t);
                x <<= 1;
                x ^= t;
            }
        }
        printf("%d\n", dp[x]);
    }
    return 0;
}

这篇关于算法竞赛进阶指南-0x02-费解的开关的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！