习题6-12 筛子难题 UVa810

1.题目描述：点击打开链接

2.解题思路：本题是迷宫问题，典型的BFS解法。不过首先应当确定状态是什么。根据题意描述：筛子的坐标+筛子的前面和顶面即构成了一个状态。这样以来，其实本题有点类似于隐式图的搜索。那么状态是怎么逐步扩展的呢？由于筛子每次都有四个方向可以滚动，因此通过判断滚动后的新状态是否合法即可扩展开来。不过向左，向右滚动需要提前打表，列出24种顶面是u，正面是f的右侧面值。详细部分见代码注释。

3.代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
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, g[N][N];
int vis[N][N][7][7];
int to[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];//向左
}
typedef pair<int, int>P;
vector<P>ans;
void print(int u)//递归寻找根结点，好处是入队列顺序正好是顺序的，不过只适用于路径较短的情况
{
if (u == -1)return;
print(q[u].pre);
ans.push_back(P(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(P(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 Possiblen");
}
int main()
{
//freopen("t.txt", "r", stdin);
to[1][2] = 4; to[1][3] = 2; to[1][4] = 5; to[1][5] = 3;//打表，to[u][f]表示顶面是u，正面是f时的右侧面的值
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;
}

最后

以上就是贤惠小甜瓜为你收集整理的习题6-12 筛子难题 UVa810的全部内容，希望文章能够帮你解决习题6-12 筛子难题 UVa810所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。