Problem 3 骰子游戏
程序员文章站
2022-07-07 10:40:52
...
背景
机房里面的人最爱玩游戏，这句活说的一点也不错，每天都会有人设计出一种新的小游戏。。。
问题描述
分析：
WZOI 的LZYP 大牛设计出一款小游戏。这个游戏地图是一个由N 行N 列的棋盘组成的（每一个小格都是1×1 正方形），如右图就是一个5×5
的的地图。LZYP 手中有一枚正方体，这枚正方体的棱长恰好为1。也就是说，这枚这正方体恰好可以覆盖一个棋盘格子。在正方体的每一个面上分别标上了一个非负整数W，当然正方体的六个面上的数字不一定相同。现在将这枚正方体放在棋盘上（恰好覆盖一个格子），一个人可以你在棋盘上滚动该立方体（立方体可以向其前、后、左、右四个方向滚动）。在滚动的过中，立方体底部与棋盘接触的那个面上的数字被加入总和S。LZYP
想要知道该怎样滚动这个正方体，才能使正方体从一个格子滚动到另一个格子得到的S 值最小。LZYP 想要知道这个最小值S，当然他会告诉你起始格子和目标格子的坐标。注意：立方体在起始格子和目标格子上的地面数字也要被计入总和，起始格子和目标格子是不同的。为了刁难你，LZYP
决定问你T 个问题，当然每次你都需要正确告诉他答案是多少；否则他就会一直烦着你，那么你就无法安心刷水题了。
输入格式
输入数据第一行包含三个整数N，T（分别用一个空格隔开），分别表示棋盘有N 行N 列，总共会有T 个问题；
第二行有6 个整数，表示立方体在开始格子上各个面上的6 个数字，顺序是：前面、后面、上面、右面、下面、左面。这6 个整数用空格隔开。
接下来 T行，每行四个整数 x1,y1,x2,y2，表示起始格子和目标格子的坐标（注意第一个是列号，第二个是行号）。输入数据保证会有一条路径从起始格子到达目标格子。
输出格式
输出数据总共T 行，每行一个整数S，表示从起始格子到目标格子的最小和。
样例输入输出 Sample #1
cube.in
5 1
0 8 1 2 1 1
5 2 5 3
cube.out
5
Sample #2
cube.in
5 1
1 1 1 1 1 1
1 2 2 3
cube.out
3
样例解释
对于Sample #1，一条可行的路径就是(5,2)(4,2)(4,1)(5,1)(5,2)(5,3)，底面的数字
分别为1,1,0,1,1,1。
对于Sample #2，一条可行的路径就是(1,2)(2,2)(2,3)，底面的数字分别为1,1,1。
数据规模 对于20%的数据，N≤10，0≤W≤10；
对于50%的数据，N≤50，0≤W≤100；
对于100%的数据，N≤100，0≤W≤1000。
对于100%的数据，T≤10.
时间限制
1s
提示
正方体的滚动是指，沿着底面与棋盘格子的一个公共边翻转。每个格子可以走多次，并且
每走一次，需要累加相应的权值。 分析：
题目来源：改编自Ural 1016 Cube on the Walk
题目大意：给你一个N×N 的棋盘和一个立方体（每个面上有一个数字），将这个立方体从一个格子滚到另一个格子，要求输出最小的权值。
考察算法 拆点 广搜
算法一
算法一
这是一道十分不错的广搜题目，它不同于一般的地图遍历。由于使用立方体的滚动来实现路径的形成，这就意味着每一个点会出现多种状态。同样这也就告诉我们这道题目需要拆点广搜。
我们不妨设这个立方体的前面、后面、上面、右面、下面、左面的标号分别为1,2,3,4,5,6。那么简单分析之后我们会发现只有以下24 种不同的状态：
123456,124563,125634,126345,213654,214365,215436,216543,
351624,352416,354162,356241,461325,462513,463251,465132,
531426,532614,534261,536142,641523,642315,643152,645231.
然后我们每一次滚动的时候做出相应的状态变化即可，具体实现可以参见程序，最后的答案就是min{dis[ex,ey,k] |k∈[1,24]}。
这道题目的难点就在于要想到拆点进行广搜，还需要有很强的实现能力。
时间复杂度：O（24*TN2） 空间复杂度：O（24*N2） 期望得分：100 分
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100+5;
const int size=262143,INF=2000000000;//262143是2^18-1(1<<18-1)。
int c[5][7]={{0,0,0,0,0,0},{0,1,2,6,3,4,5},{0,5,3,1,4,2,6},{0,1,2,4,5,6,3},{0,3,5,2,4,1,6}};
int state[25]={0,123456,124563,125634,126345,213654,214365,
215436,216543,351624,352416,354162,356241,
461325,462513,463251,465132,531426,532614,
534261,536142,641523,642315,643152,645231};
int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};
struct node{
int x,y,k;
int a[7];
};
int dis[maxn][maxn][25];
bool v[maxn][maxn][25];
node q[size];
int sx,sy,ex,ey,k;
int head,tail,n,ans,test;
int d[7],t[7];
int number()
{
int i,x;
x=0;
for(i=1;i<=6;i++)
x=x*10+t[i];
for(i=1;i<=24;i++)
if(x==state[i]) return i;
return 0;
}
void bfs()
{
int i,j;
node now,tmp;
head=0;
tail=1;
memset(dis,0x7f,sizeof(dis));
q[1].x=sx;q[1].y=sy;q[1].k=0;
for(i=1;i<=6;i++) q[1].a[i]=i;
dis[sx][sy][0]=d[5];
memset(v,0,sizeof(v));
while(head<tail)
{
head=(head&size)+1;
now=q[head];
for(i=1;i<=4;i++)
{
tmp.x=now.x+dx[i];
tmp.y=now.y+dy[i];
if(tmp.x<1||tmp.x>n) continue;
if(tmp.y<1||tmp.y>n) continue;
for(j=1;j<=6;j++)
t[j]=now.a[c[i][j]];
k=number();
if(dis[tmp.x][tmp.y][k]>dis[now.x][now.y][now.k]+d[t[5]])
{
dis[tmp.x][tmp.y][k]=dis[now.x][now.y][now.k]+d[t[5]];
if(!v[tmp.x][tmp.y][k])
{
v[tmp.x][tmp.y][k]=true;
tail=(tail&size)+1;
q[tail].x=tmp.x; q[tail].y=tmp.y; q[tail].k=k;
memcpy(q[tail].a,t,sizeof(t));
}
}
}
v[now.x][now.y][now.k]=false;
}
ans=INF;
for(i=1;i<=24;i++)
if(dis[ex][ey][i]<ans) ans=dis[ex][ey][i];
}
int main()
{
int i;
freopen("cube.in","r",stdin);
freopen("cube.out","w",stdout);
scanf("%d%d",&n,&test);
for(int i=1;i<=6;i++)
scanf("%d",&d[i]);
for(i=1;i<=test;i++)
{
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
bfs();
printf("%d\n",ans);
}
return 0;
}