ZOJ 3050 Die Board Game (bfs)

ZOJ 3050 Die Board Game

色子在坐标上滚动，给定起始点的位置和状态，看看能不能从起点走到终点并且和题目中给出的终点状态一样，求出最少步数的，n,m<=100.

刚开始我是一点想法都没有，后来看了网上的解题报告，说是每个坐标上都有24种状态，我们可以将带有状态的地图看成一个三维的map[i][j][state]，这样就可以通过广搜来解决了，我又无语了，这都是谁想出来的啊，这么巧妙，刚开始由于不知道状态之间怎样转换，昨天想到了，就在今天早上A掉~

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<queue>
#define NM 100
using namespace std;
char map[NM + 10][NM + 10];
int flag[NM + 10][NM + 10][6][6];
int dir[4][2] = {1,0,0,1,0,-1,-1,0};//4个方向
struct node
{
    int front;
    int top;
    int left,right;
    int back,bottom;
    int x,y;
    int ceng;
}t,d,start,end;
void in( struct node & t)//输入太长了,就用一个函数替代了
{
    cin >> t.top >> t.bottom >> t.back;
    cin >> t.front >> t.left >> t.right;
}
node roll( node t,int i)//以第i的方向,对t进行滚动
{
    int m;
    t.x += dir[i][0];
    t.y += dir[i][1];
    if( i == 0 )
    {
        m = t.front;
        t.front = t.top;
        t.top = t.back;
        t.back = t.bottom;
        t.bottom = m;
    }
    if( i == 1 )
    {
        m = t.right;
        t.right = t.top;
        t.top = t.left;
        t.left = t.bottom;
        t.bottom = m;
    }
    if( i == 2 )
    {
        m = t.right;
        t.right = t.bottom;
        t.bottom = t.left;
        t.left = t.top;
        t.top = m;
    }
    if( i == 3 )
    {
        m = t.bottom;
        t.bottom = t.back;
        t.back = t.top;
        t.top = t.front;
        t.front = m;
    }
    return t;
}
int main(void)
{
    int n,m,i,j;
    queue<struct node> q;
    while( cin >> n >> m )
    {
        getchar();
        for( i = 0; i < n; i++ ,getchar() )
            for( j = 0; j < m; j++ )
                cin >> map[i][j];
        cin>> start.x >> start.y >> end.x >> end.y;
        in(start);in(end);

        memset( flag,0,sizeof(flag) );
        flag[ start.x ][ start.y ][ start.front ][ start.top ] = 1;
        start.ceng = 0;
        q.push( start );
        while( !q.empty() )//bfs过程开始
        {
            t = q.front();q.pop();

            if( t.x  ==  end.x && t.y == end.y &&
                t.top==end.top && t.front==end.front )
                break;
            for( i = 0; i < 4; i++ )
            {
                d = roll(t,i);
                if( d.x >= 0 && d.x < n &&
                    d.y >= 0 && d.y < m &&
                    map[d.x][d.y] != '#' &&
                    !flag[d.x][d.y][d.front][d.top] )
                    {
                        flag[d.x][d.y][d.front][d.top] = 1;
                        d.ceng++;
                        q.push(d);
                    }//当在界内,并且状态没有达到过的时候可以入队

            }
        }

        while( !q.empty() ) q.pop();
        if( t.x  ==  end.x && t.y == end.y &&
            t.top==end.top && t.front==end.front )
            cout << t.ceng <<endl;
        else
            cout << "-1" << endl;
    }
    return 0;
}