UVA 810 A Dicey Promblem 筛子难题 （暴力BFS+状态处理）

读懂题意以后还很容易做的，

和AbbottsRevenge类似加一个维度，筛子的形态，可以用上方的点数u和前面的点数f来表示，相对的面点数之和为7，可以预先存储u和f的对应右边的点数，点数转化就很容易了。

具体做法看代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = ;

const int maxd = ;

int g[maxn][maxn];

bool vis[maxn][maxn][maxd][maxd];

struct State

{

    int x,y,u,f,pre;

}Q[];

int tor[maxd][maxd];

inline void trans(int u,int f,int i,int &nu,int &nf)

{

    if(i == ){ nu = f; nf = -u; return; }

    if(i == ){ nu =  - tor[u][f]; nf = f; return; }

    if(i == ){ nu =  - f; nf = u ; return; }

    nu = tor[u][f]; nf = f;

}

vector<int> ans;

void print_ans(int rst){

    for(int i = rst ; ~i; i = Q[i].pre){

        ans.push_back(i);

    }

    vector<int>::reverse_iterator ri = ans.rbegin(),ed = ans.rend();

    int cnt = ;

    for( ed--; ri != ed; ri++,cnt++){

        printf("(%d,%d),",Q[*ri].x,Q[*ri].y);

        if(!(cnt%)) printf("\n  ");

    }

    printf("(%d,%d)\n",Q[*ed].x,Q[*ed].y);

}

void bfs(int sx,int sy,int su,int sf)

{

    const int dx[] = {-,,,};

    const int dy[] = {,,,-};

    int head,rear;

    head = rear = ;

    Q[rear].u = su; Q[rear].f = sf; Q[rear].x = sx; Q[rear].y = sy; Q[rear].pre = -;

    rear++;

    while(head<rear){

        State &u = Q[head];

        for(int i = ; i < ; i++){

            int nx = u.x + dx[i], ny = u.y + dy[i];

            if(~g[nx][ny] && u.u != g[nx][ny]) continue;//0也不满足条件

            if(nx == sx && ny == sy){

                Q[rear].x = nx; Q[rear].y = ny;

                Q[rear].pre = head;

                ans.clear();

                print_ans(rear);

                return;

            }

            int nu,nf;

            trans(u.u,u.f,i,nu,nf);

            if(vis[nx][ny][nu][nf]) continue;

            vis[nx][ny][nu][nf] = true;

            Q[rear].u = nu; Q[rear].f = nf; Q[rear].x = nx; Q[rear].y = ny; Q[rear].pre = head;

            rear++;

        }

        head++;

    }

    printf("No Solution Possible\n");

}

int main()

{

   // freopen("in.txt","r",stdin);

    char str[];

    tor[][] = ; tor[][] = ; tor[][] = ; tor[][] = ;

    tor[][] = ; tor[][] = ; tor[][] = ; tor[][] = ;

    tor[][] = ; tor[][] = ; tor[][] = ; tor[][] = ;

    tor[][] = ; tor[][] = ; tor[][] = ; tor[][] = ;

    tor[][] = ; tor[][] = ; tor[][] = ; tor[][] = ;

    tor[][] = ; tor[][] = ; tor[][] = ; tor[][] = ;

    const int bsz = sizeof(bool)*maxn*;

    const int isz = sizeof(int)*maxn;

    while(~scanf("%s",str)&& strcmp(str,"END")){

        printf("%s\n  ",str);

        int R,C,sx,sy,su,sf;

        scanf("%d%d%d%d%d%d",&R,&C,&sx,&sy,&su,&sf);

        memset(vis,,bsz*(R+));

        for(int i = ; i <= R; i ++){

            for(int j = ; j <= C; j++)

                scanf("%d",g[i]+j);

        }

        memset(g[R+],,isz);

        for(int i = ; i <= R; i++) g[i][C+] = ;

        bfs(sx,sy,su,sf);

    }

    return ;

}