UVA810 筛子难题 A Dicey Problem

48 阅读 0 评论 32 点赞

我是靠谱客的博主甜甜香烟，最近开发中收集的这篇文章主要介绍UVA810 筛子难题 A Dicey Problem，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

知识点：广搜

一个寻找路径的问题，题目的pdf里面说了，筛子能够移动的规则是top的数字和要移动的位置上的数字相同或者是-1，不是移动之后地图数字和与它挨着的，也就是筛子最底面的数字相同，这里刘汝佳的翻译好像就是这个意思，是错的，保证，要么只有一条路径能够回到起点，要么没有，所以题目保证的是有唯一解或者没有解，不会是多解，无权图的最短路可以用bfs来实现，但是为什么能用最短路求唯一的路径还是想不明白

一个难点就是状态怎么转换，很明显状态是四维的，除了坐标，还有筛子的顶面前面，只看顶面前面就能唯一确定一个筛子的状态，这里一个很重要的规律就是两个想对的筛子和是7，假如x第一行是1，向x增大的方向是前面，也就是向前转，向前转，原来的top变为了front，原来的7-front变为了top，向后转同理，这个情况稍微简单一点，然后是向左向右转，假如每种形态（上前确定）我们记录它左边的点数，当然右边的也可以，那么左转front不变，top变为7-原来左边的点数，右转front不变，top变为原来左边的点数，这样就可以把状态转换的数组预先处理出来了，

接下来就是广搜，然后打印路径了，这里打印路径用的是循环的方法，并且用结构体保存数据，和之前用数组保存相比有很大改进，然后既然题目说的只有一条路径，那么udebug上面的数据应该是不合标准的，因为它最少可以有两个能回到终点的路径

#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pa;

struct state {
    int x, y, top, front;
    state() {}
    state(int a, int b, int c, int d): x(a), y(b), top(c), front(d) {}
};

int n, m, r, c, f1, f2, mat[15][15], rec[10][10];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1}; //前后左右
state pre[15][15][10][10];

void init() {
    rec[1][2] = 4; rec[1][3] = 2; rec[1][5] = 3; rec[1][4] = 5;
    rec[2][1] = 3; rec[2][4] = 1; rec[2][6] = 4; rec[2][3] = 6;
    rec[3][1] = 5; rec[3][2] = 1; rec[3][6] = 2; rec[3][5] = 6;
    rec[4][1] = 2; rec[4][5] = 1; rec[4][6] = 5; rec[4][2] = 6;
    rec[5][1] = 4; rec[5][3] = 1; rec[5][6] = 3; rec[5][4] = 6;
    rec[6][2] = 3; rec[6][4] = 2; rec[6][5] = 4; rec[6][3] = 5;
}

void print(state u) {
    vector<pa> ans;
    while (true) {
        ans.pb(mk(u.x, u.y));
        if (u.x == r && u.y == c) break;
        u = pre[u.x][u.y][u.top][u.front];
    }
    reverse(all(ans));
    ans.pb(mk(r, c));
    for (int i = 0; i < sz(ans); i++) {
        if (i % 9 == 0) cout << "  ";
        cout << "(" << ans[i].fi << "," << ans[i].se << ")";
        if (i < sz(ans) - 1) cout << ',';
        if (i % 9 == 8 || i == sz(ans) - 1) cout << endl;
    }
}

void bfs() {
    queue<state> q;
    q.push(state(r, c, f1, f2));
    int vis[15][15][10][10] = {};
    int cnt = 1;
    while (!q.empty()) {
        state now = q.front();
        q.pop();
        if (now.x == r && now.y == c && cnt++ != 1) {
            print(pre[now.x][now.y][now.top][now.front]);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int x = now.x + dx[i];
            int y = now.y + dy[i];
            if (x < 1 || x > n || y < 1 || y > m) continue;
            int top, front;
            if (i == 0) { top = 7 - now.front; front = now.top; }
            if (i == 1) { top = now.front; front = 7 - now.top; }
            if (i == 2) { top = 7 - rec[now.top][now.front]; front = now.front; }
            if (i == 3) { top = rec[now.top][now.front]; front = now.front; }
            if ((now.top == mat[x][y] || mat[x][y] == -1) && !vis[x][y][top][front]) {
                q.push(state(x, y, top, front));
                vis[x][y][top][front] = 1;
                pre[x][y][top][front] = now;
            }
        }
    }
    cout << "  No Solution Possiblen";
}

int main() {
    init();
    string maze;
    while (cin >> maze && maze != "END") {
        cin >> n >> m >> r >> c >> f1 >> f2;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) cin >> mat[i][j];
        }
        cout << maze << endl;
        bfs();
    }
    return 0;
}