专栏首页饶文津的专栏【USACO 3.2】Magic Squares

【USACO 3.2】Magic Squares

题意

4*2个格子分别为 1234 8765 的魔板有3种操作,A:上下两排互换,B:最后一列放到第一列前面,C:中间四个顺时针旋转1格。 现在给出目标状态,找出最少步数可从原始状态到达目标状态,且输出最小字典序的操作序列。

题解

代码

/*
USER:19flipp1
TASK:msquare
LANG:C++
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define in(s) freopen(#s".in","r",stdin);freopen(#s".out","w",stdout);
#define N 10
using namespace std;
int a[N],fac[N];
struct node{
    int a[N];
    int d;
    char s[25];
}nd;
bool vis[320000];
int cantor(int a[N]){
    int ans=0,c;
    for(int i=1;i<8;i++){
        c=0;
        for(int j=i;j<=8;j++)if(a[i]>a[j])c++;
        ans+=fac[8-i]*c;
    }
    return ans;
}
void work(int a[],int i){
    if(i==0){
        for(int j=1;j<=4;j++)swap(a[j],a[9-j]);
    }else if(i==1){
        int t=a[1];
        a[1]=a[4],a[4]=a[3],a[3]=a[2],a[2]=t;
        t=a[5];
        a[5]=a[6],a[6]=a[7],a[7]=a[8],a[8]=t;
    }else if(i==2){
        int t=a[2];
        a[2]=a[7];a[7]=a[6];a[6]=a[3];a[3]=t;
    }
}
void bfs(){
    queue<node> q;
    node p;
    for(int i=1;i<=8;i++)p.a[i]=i;
    p.d=0;
    q.push(p);
    while(!q.empty()){
        node p=q.front();
        q.pop();
        int ok=1;
        for(int i=1;i<=8;i++)if(p.a[i]!=nd.a[i]){ok=0;break;}
        if(ok){
            printf("%d\n",p.d);
            for(int i=1;i<=p.d;i++)
                printf("%c",p.s[i]);
            puts("");
            break;
        }
        for(int i=0;i<3;i++){
            node np=p;
            work(np.a,i);
            int num=cantor(np.a);
            if(!vis[num]){
                vis[num]=1;
                np.d++;
                np.s[np.d]='A'+i;
                q.push(np);
            }
        }
    }
}
int main(){
    in(msquare);
    fac[0]=1;
    for(int i=1;i<=8;i++){
        scanf("%d",&nd.a[i]);
        fac[i]=fac[i-1]*i;
    }
    bfs();
    return 0;
}

代码2

/*
USER:19flipp1
TASK:msquare
LANG:C++
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define in(s) freopen(#s".in","r",stdin);freopen(#s".out","w",stdout);
#define N 10
using namespace std;
int a[N],fac[N];
struct node{
    int a[N];
    int d;
    char s[25];
}nd;
bool vis[8][8][8][8][8][8][8];
void work(int a[],int i){
    if(i==0){
        for(int j=1;j<=4;j++)swap(a[j],a[9-j]);
    }else if(i==1){
        int t=a[1];
        a[1]=a[4],a[4]=a[3],a[3]=a[2],a[2]=t;
        t=a[5];
        a[5]=a[6],a[6]=a[7],a[7]=a[8],a[8]=t;
    }else if(i==2){
        int t=a[2];
        a[2]=a[7];a[7]=a[6];a[6]=a[3];a[3]=t;
    }
}
bool Vis(int a[]){
    bool &t=vis[a[1]-1][a[2]-1][a[3]-1][a[4]-1][a[5]-1][a[6]-1][a[7]-1];
    if(t)return 1;
    t=1;
    return 0;
}
void bfs(){
    queue<node> q;
    node p;
    for(int i=1;i<=8;i++)p.a[i]=i;
    p.d=0;
    q.push(p);
    while(!q.empty()){
        node p=q.front();
        q.pop();
        int ok=1;
        for(int i=1;i<=8;i++)if(p.a[i]!=nd.a[i]){ok=0;break;}
        if(ok){
            printf("%d\n",p.d);
            for(int i=1;i<=p.d;i++)
                printf("%c",p.s[i]);
            puts("");
            break;
        }
        for(int i=0;i<3;i++){
            node np=p;
            work(np.a,i);
            if(!Vis(np.a)){
                np.d++;
                np.s[np.d]='A'+i;
                q.push(np);
            }
        }
    }
}
int main(){
    in(msquare);
    fac[0]=1;
    for(int i=1;i<=8;i++){
        scanf("%d",&nd.a[i]);
        fac[i]=fac[i-1]*i;
    }
    bfs();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 弱校联盟10.3

    n对括号最多需要1+2+..+n次交换,当它是)))..(((的形式时,)))(((需要6次,然后把中间两个交换一下,))()((就还需要5次,再交换一次靠近左...

    饶文津
  • 【CodeForces 504A】Misha and Forest

    有n个点,代号分别为0到n-1,然后第i个点有di个相连点,与i 相连的点的XOR sum 为si,求所有的边。

    饶文津
  • 「AtCoder Grand018B」Sports Festival(暴力)

    饶文津
  • 弱校联盟10.3

    n对括号最多需要1+2+..+n次交换,当它是)))..(((的形式时,)))(((需要6次,然后把中间两个交换一下,))()((就还需要5次,再交换一次靠近左...

    饶文津
  • 牛客小白月赛11D(分治、RMQ)

    定义一个玄学节点叫做 R,每次操作读入 val ,执行 Insert(R,val)。

    ACM算法日常
  • 颜色聚合向量

    package com.imageretrieval.features; /** * 颜色聚合向量<br> * 参考链接:http://www.docin...

    Venyo
  • 每天一算: Number of Boomerangs

    五分钟学算法
  • 2018 团队设计天梯赛题解---华山论剑组

    2018 年度的团队设计天梯赛前几天结束了。但是成绩真的是惨不忍睹。。。毕竟是团队的比赛,如果团队平均水平不高的话,单凭一个人,分再高也很难拉起来(当然,一个人...

    指点
  • BZOJ2655: calc(dp 拉格朗日插值)

    设\(f[i][j]\)表示选了\(i\)个严格递增的数最大的数为\(j\)的方案数

    attack
  • OpenCV图像处理专栏十 | 利用中值滤波进行去雾

    这是OpenCV图像处理专栏的第十篇文章,介绍一种利用中值滤波来实现去雾的算法。这个方法发表于国内的一篇论文,链接我放附录了。

    BBuf

扫码关注云+社区

领取腾讯云代金券