骰子

· · 个人记录

骰子

【问题描述】

一个 N \times M 的矩形迷宫左上角的格子里放了一个骰子。骰子的 展开图如图所示

其中，１对应的是上侧面（就是当你俯视这个骰 子的时候正对你的那个面）。２对应的是左侧面。骰子的每个面的。

大小和迷宫的每个小格的大小相同。骰子可以在迷宫的棋盘上翻动到相邻的格子。但是不能翻出迷宫的边界。

你的任务是找到一条通路，使得骰子能从迷宫的左上角翻到右下角，且到达目的地时的上侧面上的数值最大。骰子可以经过同一个格子若干次。

【数据输入】

第一行有两个整数 N,M(2 \leq N,M \leq 50)，表示迷宫的高度和宽度。 后面 N 行是一个 N \times M 的矩阵，矩阵的元素为0 或1，0 表示空的格 子，1 表示有障碍物的格子。左上角的那个格子（起始格）总是为0。

【数据输出】

第一行一个整数 W，表示从起点到终点经过路径的长度。 后面 W 行表示从起点出发后，经过的格子的坐标。 如果无法到达终点，则输出-1。

PS:由于搜索路径不唯一，所以规定搜索顺序为右→下→左→上

【样例输入】

3 2

0 1

0 0

0 0

【样例输出】

3

2 1

2 2

3 2

【数据范围】

对于30\%的数据，2 \leq N,M \leq 10;

对于100\%的数据，2 \leq N,M \leq 50;

Solution

就是一个广度优先搜索，只是标记入队状态很难标记。

学过小学数学的都知道， 一个骰子的前面、上面、左面知道了，整个骰子的形态就确定了（因为任何一个面与背面的点数加起来为7）

不多说，直接上代码。

code：

#include<cstdio>
#include<queue>
#define N 50
#define M 50
using namespace std;
struct qianqu{
    int x,y;
}pre[N+10][N+10];
struct node{
    int x,y,top,left,front,step;
};
queue<node>q;
int n,m,map[N+10][M+10],fx[4]={0,1,0,-1},fy[4]={1,0,-1,0},ans=-1,ans_step;
bool vis[N+10][N+10][7][7];/*vis[x][y][a][b]表示坐标为x，y的点上侧面为a，左侧面为b的情况
是否被搜索过*/
int next_top(int top,int left,int front,int f)
{
    if(f==0)return left;
    if(f==1)return 7-front;
    if(f==2)return 7-left;
    if(f==3)return front;
}
int next_left(int top,int left,int front,int f)
{
    if(f==0)return 7-top;
    if(f==1)return left;
    if(f==2)return top;
    if(f==3)return left;
}
int next_front(int top,int left,int front,int f)
{
    if(f==0)return front;
    if(f==1)return top;
    if(f==2)return front;
    if(f==3)return 7-top;
}
void print(int x,int y)
{
    if(x==1&&y==1)return;
    print(pre[x][y].x,pre[x][y].y);
    printf("%d %d\n",x,y);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&map[i][j]);
    q.push((node){1,1,1,2,4,0});
    vis[1][1][1][2]=1;
    node temp;int dx,dy,dfront,dtop,dleft;
    while(!q.empty())
    {
        temp=q.front();q.pop();
        for(int i=0;i<=3;i++)
        {
            dx=temp.x+fx[i];dy=temp.y+fy[i];
            dleft=next_left(temp.top,temp.left,temp.front,i);
            dtop=next_top(temp.top,temp.left,temp.front,i);
            dfront=next_front(temp.top,temp.left,temp.front,i);
            if(dx<1||dx>n||dy<1||dy>m)continue;//边界
            if(dx==n&&dy==m)//到终点
            {
                if(ans<=dtop)
                {
                    if(ans<dtop){
                        pre[n][m].x=temp.x;pre[n][m].y=temp.y;
                        ans=dtop;ans_step=temp.step+1;
                        /*printf("%d   %d\n",ans_step,ans);
                        print(n,m);*/
                    }
                    if(ans==dtop&&ans_step>temp.step+1)//更新路径长度 
                    {
                        pre[n][m].x=temp.x;pre[n][m].y=temp.y;
                        ans_step=temp.step+1;
                    }
                }
                continue;//一定要跳过终点，否则pre数组会形成环，然后报错 
            }
            if(!vis[dx][dy][dtop][dleft]&&map[dx][dy]==0)//能走
            {
                vis[dx][dy][dtop][dleft]=1;
                pre[dx][dy].x=temp.x;pre[dx][dy].y=temp.y;
                q.push((node){dx,dy,dtop,dleft,dfront,temp.step+1});
            }
        }
    }
    if(ans==-1)printf("%d",ans);
    else
    {
        printf("%d\n",ans_step);
        print(n,m);
    }
    return 0;
}