Problem 3 骰子游戏

xiaoxiao2021-02-28  103

背景 机房里面的人最爱玩游戏,这句活说的一点也不错,每天都会有人设计出一种新的小游 戏。。。 问题描述 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; }
转载请注明原文地址: https://www.6miu.com/read-52452.html

最新回复(0)