GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版
题目并不算难,但是有一些需要注意的事情。
1. 骰子样式是确定的,而且题目中的图示正确的。
2. 根据骰子的两个相邻的面(例如题目给出的正面和顶面),可以确定整个骰子在桌面的每个面的位置。但是这个位置确定以及骰子在转动时的转换关系有点难找到规律。我用的一种比较繁琐的(但容易理解的)方式确定转动后骰子的位置。
3. 题目中并未限制骰子经过重复的点,也就是说每个点可以走多次。一开始我以为不能重复走。样例中的第二个迷宫就碰到了重复走的(2,2)结点。
4. 虽然可以重复走,但是如果不加以限制,那么会造成死循环,一直找不到终点。我一开始加的条件是在位置重复时,进入的方向不能一致,然后报错。后面又试了骰子面的位置不能一致,即顶面和正面位置不能一致,就对了。如果设置方向不能一致+骰子面的位置不能一致,那么还会进入死循环。我的理解是,即使进入的时候方向不一致,只要进入后骰子面的位置一致了,那么它随后进入其他结点的判断条件是一致的,即应该不能重复进入,给与限制。
5. 题目中提到在存在路径的情况下是唯一解,因此我们只需要用深度优先遍历一次就可以了。这里注意,uDebug中的部分例子不止存在一个解。
6. 由于最后需要输出路径,因此我们需要记录经过的每一个位置和方向。我使用了一个二维数组记录了经过每个位置时的方向。最后根据终点回溯到起点即可。这里注意,由于位置可以重复进入,因此只记录方向是不够的,还必须记录顺序,即第一次经过,第二次经过要进行顺序的区分。
我使用的判断骰子位置的方法:
1. 首先按照顺序,把每一个骰子周围的结点都记录下来,按照“顺时针 上 右 下 左 背”的顺序。这样就总结出了骰子面之间的关系。
2. 另正面和顶面以及方向作为输入,计算新的顶面和正面。
在确定了正面的情况下,一个骰子的顶面可能是正面的四个邻边的每一个。而我们又整理了上面的关系。根据这些就可以判断。例如:
在骰子面关系中的顶面就是实际的顶面时,如果向右移动,此时顶面就是原来的左面。
在骰子面关系中的左面就是实际的顶面时,如果向右移动,此时顶面就是原来的下面。
这个判断需要根据每种邻边位置和每个转动分别判断,因此比较繁琐。但是如果画个图分析,这个关系还是非常清晰的。
#include<string>
#include<string.h>
#include<iostream>
#include<vector>
using namespace std;
struct PATH {
int p;
int top, face;
};
int graph[12][12];
vector<PATH> path[12][12];
int row, column;
int startr, startc;
bool flag, startFlag;
// 下 右 上 左
int Step[5][2] = {{}, {1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int pathArr[110][2];
int pathLen;
// 顺时针 上 右 下 左 背
int Die[7][5] = {
{},
{5, 3, 2, 4, 6},
{1, 3, 6, 4, 5},
{1, 5, 6, 2, 4},
{6, 5, 1 ,2, 3},
{3, 1, 4, 6, 2},
{3, 5, 4, 2, 1},
};
bool judgeStep(int r, int c) {
if(r <= 0 || r > row) return false;
if(c <= 0 || c > column) return false;
return true;
}
void getDieStatus(int top, int face, int step, int *topn, int *facen) {
// 顺着放的
if(Die[face][0] == top) {
switch(step) {
case 1:
*facen = Die[face][0];
*topn = Die[face][4];
break;
case 2:
*facen = face;
*topn = Die[face][3];
break;
case 3:
*facen = Die[face][2];
*topn = face;
break;
case 4:
*facen = face;
*topn = Die[face][1];
break;
}
return;
}
if(Die[face][2] == top) {
// 逆着放的
switch(step) {
case 1:
*facen = Die[face][2];
*topn = Die[face][4];
break;
case 2:
*facen = face;
*topn = Die[face][1];
break;
case 3:
*facen = Die[face][0];
*topn = face;
break;
case 4:
*facen = face;
*topn = Die[face][3];
break;
}
return;
}
if(Die[face][3] == top) {
// 左侧的当顶
switch(step) {
case 1:
*facen = Die[face][3];
*topn = Die[face][4];
break;
case 2:
*facen = face;
*topn = Die[face][2];
break;
case 3:
*facen = Die[face][1];
*topn = face;
break;
case 4:
*facen = face;
*topn = Die[face][0];
break;
}
return;
}
if(Die[face][1] == top) {
// 左侧的当顶
switch(step) {
case 1:
*facen = Die[face][1];
*topn = Die[face][4];
break;
case 2:
*facen = face;
*topn = Die[face][0];
break;
case 3:
*facen = Die[face][3];
*topn = face;
break;
case 4:
*facen = face;
*topn = Die[face][2];
break;
}
return;
}
}
bool judgePath(int r, int c, int step, int top, int face) {
for(int i = 0; i < path[r][c].size(); ++i) {
if(path[r][c][i].top == top && path[r][c][i].face == face) return false;
}
return true;
}
void work(int r, int c, int top, int face) {
if(startFlag && r == startr && c == startc) {
flag = true;
return;
}
startFlag = true;
// cout << r << " " << c << endl;
int i, j, rn, cn, topn, facen;
for(i = 1; i < 5; ++i) {
rn = r + Step[i][0];
cn = c + Step[i][1];
if(!judgeStep(rn, cn)) continue;
if(flag) return;
if(graph[rn][cn] != -1 && graph[rn][cn] != top) continue;
getDieStatus(top, face, i, &topn, &facen);
if(!judgePath(rn, cn, i, topn, facen)) continue;
path[rn][cn].push_back({i, topn, facen});
work(rn, cn, topn, facen);
if(flag) return;
path[rn][cn].pop_back();
}
}
void getPathArr() {
int r, c, rn, cn;
int i, j, k, step;
pathLen = 0;
r = startr, c = startc;
do {
pathArr[pathLen][0] = r;
pathArr[pathLen][1] = c;
++pathLen;
step = path[r][c][path[r][c].size() - 1].p;
rn = r-Step[step][0];
cn = c-Step[step][1];
// cout << path[r][c].size() - 1 << " " << rn << " " << cn << endl;
path[r][c].pop_back();
r = rn;
c = cn;
} while(r != startr || c != startc);
pathArr[pathLen][0] = r;
pathArr[pathLen][1] = c;
++pathLen;
}
int main() {
string line;
int top, face;
int i, j, k;
while(cin >> line && line != "END") {
cout << line << endl;
cin >> row >> column >> startr >> startc >> top >> face;
for(i = 1; i <= row; ++i) {
for(j = 1; j <= column; ++j) {
cin >> graph[i][j];
path[i][j] = vector<PATH>();
}
}
flag = false; startFlag = false;
work(startr, startc, top, face);
if(!flag) {
cout << " No Solution Possible" << endl;
continue;
}
getPathArr();
cout << " ";
for(i = 1; i <= pathLen; ++i) {
cout << "(" << pathArr[pathLen-i][0] << "," << pathArr[pathLen-i][1] << ")";
if(i != pathLen) cout << ",";
if(i % 9 == 0 && i != pathLen) cout << endl << " ";
}
cout << endl;
}
return 0;
}