UVA-1601 万圣节后的早晨 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

以三个点的当前位置作为状态，广度优先遍历，找到终点即为最短次数。

注意：

一次可以移动多个点，但是每个点只能移动一步。在同一次中，B可以移动到A离开前的位置上，即如果A走了，B可以去A之前的位置。因此，这三个点的移动和判断是有先后顺序的。对每个状态遍历时，情况实际上有 3的全排列（值为6），以及每个点移动的可能四种位置： 3! * 4^3。当然因为墙的存在，因此并没有这么多。

由于最高只有3，因此我的全排列写的不怎么优雅，直接嵌套循环完成了。注意每个点可以动，也可以不动，因此我们要考虑只有一个点动，两个点动的情况。写全排列时。如果第一个点动了大现已经遍历过，这时候不能放入队列（因为在其他点不动的情况下，这个状态已经遍历过了）。但是如果后面的点还继续动，那么这并不是一个完整的状态，因此不应该终止全排列。

按照上面的方法做的话，耗时很久，我扣了点细节，最后终于压线AC。（时间限制12000ms）

1. 根据题目描述，很多节点周围都是墙，因此用邻接表效率更高一些。

2. 一个点的坐标位置为1-16， x和y很容易放到一个数字中存储的。相对于每次计算x1 == x2 && y1 == y2， 一个数字的计算次数更少。其实三个结点的xy位置应该可以整合为一个数字的，这样效率会更高。 

3. 我的答案中用到了struct，一些辅助的判断函数，使用引用而不是直接将整个对象值作为参数，性能会提高一些。

#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>using namespace std;int graph[20][20];
vector<int> graphVec[300];
int w, h, n;struct Point {char ch;int pos;
};
Point initPoints[3];
Point suppPoints[3];struct Status {int pos[3];int step;
};
Status origin, terminal;bool access[300][300][300];int steps[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };bool sameLetter(char small, char big) {return small == big - 'A' + 'a';
}
bool statusEqual(Status &s1, Status &s2) {for (int i = 0; i < n; ++i) {if (s1.pos[i] != s2.pos[i]) return false;}return true;
}int xy2Num(int x, int y) {return x * 17 + y;
}void num2XY(int num, int *x, int *y) {*x = num / 17;*y = num % 17;
}bool judgeAcc(Status &s) {if (n == 1) return access[s.pos[0]][0][0];if (n == 2) return access[s.pos[0]][s.pos[1]][0];if (n == 3) return access[s.pos[0]][s.pos[1]][s.pos[2]];
}void setAcc(Status &s) {if (n == 1) access[s.pos[0]][0][0] = true;if (n == 2) access[s.pos[0]][s.pos[1]][0] = true;if (n == 3) access[s.pos[0]][s.pos[1]][s.pos[2]] = true;
}void printStatus(Status &s) {int x, y;for (int i = 0; i < n; ++i) {num2XY(s.pos[i], &x, &y);printf("[%d %d] ", x, y);}printf(" %d\n", s.step);
}void printGraphVec() {int i, j, x, y;for(i = 0; i < 300; ++i) {if(graphVec[i].size()) {num2XY(i, &x, &y);printf("%d %d - ", x, y);for(j = 0; j < graphVec[i].size(); ++j) {num2XY(graphVec[i][j], &x, &y);printf("[%d %d] ", x, y);}putchar('\n');}}putchar('\n');
}void init() {int i, j, k, initLen = 0, suppLen = 0;int x, y;memset(access, 0, sizeof(access));for(i = 0; i < 300; ++i) {graphVec[i].clear();}for (i = 1; i <= h; ++i) {while (getchar() != '\n') ;for (j = 1; j <= w; ++j)  {graph[i][j] = getchar();if (graph[i][j] >= 'a' && graph[i][j] <= 'z')initPoints[initLen++] = {char(graph[i][j]), xy2Num(i, j)};if (graph[i][j] >= 'A' && graph[i][j] <= 'Z')suppPoints[suppLen++] = {char(graph[i][j]), xy2Num(i, j)};}}for(i = 2; i < h; ++i) {for (j = 2; j < w; ++j)  {if(graph[i][j] == '#') continue;for(k = 0; k < 4; ++k) {x = i + steps[k][0];y = j + steps[k][1];if(graph[x][y] == '#') continue;graphVec[xy2Num(i, j)].push_back(xy2Num(x, y));}}}// printGraphVec();for (i = 0; i < n; ++i) {origin.pos[i] = initPoints[i].pos;for (j = 0; j < n; ++j) {if (sameLetter(initPoints[i].ch, suppPoints[j].ch)) {terminal.pos[i] = suppPoints[j].pos;break;}}}origin.step = 0;terminal.step = 0;setAcc(origin);// printStatus(origin);// printStatus(terminal);
}bool judgePos(Status &s) {int i, j;for (i = 0; i < n; ++i) {for (j = 0; j < n; ++j) {if (i == j) continue;if (s.pos[i] == s.pos[j]) return false;}}return true;
}int compute() {int i, j, k, a1, a2, a3;int num1, num2, num3, len1, len2, len3;queue<Status> qu;Status s0, s1, s2, s3;qu.push(origin);while (!qu.empty()) {s0 = qu.front();qu.pop();// putchar('\n');// printStatus(s0);s0.step++;for (i = 0; i < n; ++i) {num1 = s0.pos[i]; len1 = graphVec[num1].size();for (a1 = 0; a1 < len1; ++a1) {s1 = s0;s1.pos[i] = graphVec[num1][a1];if (!judgePos(s1)) continue;if (!judgeAcc(s1)) {// printStatus(s1);setAcc(s1); qu.push(s1);}if (statusEqual(s1, terminal)) return s1.step;for (j = 0; j < n; ++j) {if (i == j) continue;num2 = s1.pos[j]; len2 = graphVec[num2].size();for (a2 = 0; a2 < len2; ++a2) {s2 = s1;s2.pos[j] = graphVec[num2][a2];if (!judgePos(s2)) continue;if (!judgeAcc(s2)) {// printStatus(s2);setAcc(s2); qu.push(s2);}if (statusEqual(s2, terminal)) return s2.step;for (k = 0; k < n; ++k) {if (k == i || k == j) continue;num3 = s2.pos[k]; len3 = graphVec[num3].size();for (a3 = 0; a3 < len3; ++a3) {s3 = s2;s3.pos[k] = graphVec[num3][a3];if (!judgePos(s3)) continue;if (!judgeAcc(s3)) {// printStatus(s3);setAcc(s3); qu.push(s3);}if (statusEqual(s3, terminal)) return s3.step;}}}}}}}
}int main() {while (scanf("%d %d %d", &w, &h, &n) == 3 && w != 0) {init();printf("%d\n", compute());}return 0;
}