noip搜索模拟题骰子

骰子

dice.cpp/c/pas

1s/128M

【题目描述】

桌面上有两个特别的骰子。骰子的每一个面，都写了一个不同的数字。设第一个骰子上下左右前后分别为a1, a2, a3, a4, a5, a6，第二个骰子分别为b1, b2, b3, b4, b5, b6。保证每个数字在区间 [1, 6] 内，而且对于所有的i ≠ j都有ai ≠ aj, bi ≠ bj。特别地，每个骰子相对的两面数字之和都不会为7

一开始，两个骰子的摆放可能是不同的（即对应面的数字可能不同），所以Ddy想通过如下操作使两个骰子摆放变得相同

左转：以CG为轴向左转90°，使ACGE变成底部

右转：以DH为轴向右转90°，使BDHF变成底部

前转：以CD为轴向前转90°，使ABCD变成底部

后转：以GH为轴向后转90°，使EFHG变成底部

现在Ddy想知道达到目的的最小步数是多少。

【输入】

输入文件名：dice.in

多组数据，直到EOF

对于每组数据，两行，分别表示两个骰子的状态。

每行6个数分别a1, a2, …, a6和b1, b2, …, b6

【输出】

输出文件名：dice.out

对于每组数据输出一行，达到目的的最小步数。

无解则输出 -1

【输入样例】

1 2 3 4 5 6

1 2 5 6 4 3

1 2 3 4 5 6

1 4 2 5 3 6

【输出样例】

-1

题解：
因为每个骰子只有六个面，可以将这六个面的状态表示为一个六位数。（当然也可以用七进制或者六进制）

然后广搜，每一步都有四个方向可以选择，又因为每一个骰子都只有24种状态，记忆化一下就可以了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<queue>

using namespace std;

int ans,a[],b[],ok;

int make(int a[])

{

    int cnt=;

    for(int i=;i<=;i++)cnt=cnt*+a[i];

    return cnt;

}

int mmin[];

void bfs()

{

    memset(mmin,/,sizeof(mmin));

    int r=make(a),s;

    queue<int>mem;queue<int>p;

    mem.push(r);

    p.push();

    mmin[r]=;

    while(!mem.empty())

    {

        int x=mem.front(),y=p.front();mem.pop();p.pop();

        if(x==ok){ans=y;return;}

        s=x%+((x/)%)*+((x/)%)*+((x/)%)*+(x/)*;

        if(mmin[s]>y+){mem.push(s);p.push(y+);mmin[s]=y+;}

        s=x%+((x/)%)*+((x/)%)*+((x/)%)*+(x/)/;

        if(mmin[s]>y+){mem.push(s);p.push(y+);mmin[s]=y+;}

        s=(x/)%*+(x%)*+((x/)%)*+(x/)%+(x/)*;

        if(mmin[s]>y+){mem.push(s);p.push(y+);mmin[s]=y+;}

        s=(x/)%*+(x%)*+((x/)%)*+((x/)%)*+x/;

        if(mmin[s]>y+){mem.push(s);p.push(y+);mmin[s]=y+;}

    }

}

int main()

{

    freopen("dice.in","r",stdin);

    freopen("dice.out","w",stdout);

    int i,j;

    while(scanf("%d",&a[])!=EOF)

    {

        for(i=;i<=;i++)scanf("%d",&a[i]);

        for(i=;i<=;i++)scanf("%d",&b[i]);

        ok=make(b);

        ans=;

        bfs();

        if(ans!=)printf("%d\n",ans);

        else printf("-1\n");

    }

    return ;

}

骰子

noip搜索模拟题 骰子

noip搜索模拟题骰子