UVA 810 - A Dicey Problem

题意：一个骰子，给你顶面和前面。在一个起点，每次能移动到周围4格，为-1，或顶面和该位置数字一样，那么问题来了，骰子能不能走一圈回到原地，输出路径，要求最短，假设有多个最短，依照上下左右输出

思路：读懂题就是水题，就记忆化搜一下就可以，记录状态为位置和骰子顶面。正面（由于有两面就能确定骰子了）

代码：

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

const int D[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};

const int N = 15;

char str[25];

int n, m, sx, sy, u, f, to[7][7], g[N][N];

int vis[N][N][7][7];

struct State {

	int x, y, u, f;

	int pre;

	State() {}

	State(int x, int y, int u, int f, int pre) {

		this->x = x;

		this->y = y;

		this->u = u;

		this->f = f;

		this->pre = pre;

	}

} Q[10005];

void tra(int &vu, int &vf, int d) {

	if (d == 0) {int tmp = vf; vf = 7 - vu; vu = tmp;}

	if (d == 1) {int tmp = vu; vu = 7 - vf; vf = tmp;}

	if (d == 2) vu = 7 - to[vu][vf];

	if (d == 3) vu = to[vu][vf];

}

#define MP(a,b) make_pair(a,b)

typedef pair<int, int> pii;

vector<pii> ans;

void print(int u) {

	if (u == -1) return;

	print(Q[u].pre);

	ans.push_back(MP(Q[u].x, Q[u].y));

}

void bfs() {

	ans.clear();

	int head = 0, rear = 0;

	Q[rear++] = State(sx, sy, u, f, -1);

	memset(vis, 0, sizeof(vis));

	vis[sx][sy][u][f] = 1;

	while (head < rear) {

		State u = Q[head++];

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

			State v = u;

			v.x += D[i][0];

			v.y += D[i][1];

			if (v.x <= 0 || v.x > n || v.y <= 0 || v.y > m) continue;

			if (g[v.x][v.y] != -1 && u.u != g[v.x][v.y]) continue;

			if (v.x == sx && v.y == sy) {

				print(head - 1);

				ans.push_back(MP(sx, sy));

				int tot = ans.size();

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

					if (i % 9 == 0) printf("\n  ");

					printf("(%d,%d)%c", ans[i].first, ans[i].second, i == tot - 1 ?

'\n' : ',');

				}

				return;

			}

			tra(v.u, v.f, i);

			if (vis[v.x][v.y][v.u][v.f]) continue;

			vis[v.x][v.y][v.u][v.f] = 1;

			v.pre = head - 1;

			Q[rear++] = v;

		}

	}

	printf("\n  No Solution Possible\n");

}

int main() {

	to[1][2] = 4; to[1][3] = 2; to[1][4] = 5; to[1][5] = 3;

	to[2][1] = 3; to[2][3] = 6; to[2][4] = 1; to[2][6] = 4;

	to[3][1] = 5; to[3][2] = 1; to[3][5] = 6; to[3][6] = 2;

	to[4][1] = 2; to[4][2] = 6; to[4][5] = 1; to[4][6] = 5;

	to[5][1] = 4; to[5][3] = 1; to[5][4] = 6; to[5][6] = 3;

	to[6][2] = 3; to[6][3] = 5; to[6][4] = 2; to[6][5] = 4;

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

		printf("%s", str);

		scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &u, &f);

		for (int i = 1; i <= n; i++)

			for (int j = 1; j <= m; j++)

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

		bfs();

	}

	return 0;

}

秒客网

UVA 810 - A Dicey Problem(BFS）

UVA 810 - A Dicey Problem