安徽网站优化价格咨询,重庆市建设政务中心网站,蜘蛛seo超级外链工具,网站产品关键词导出GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版
以三个点的当前位置作为状态#xff0c;广度优先遍历#xff0c;找到终点即为最短次数。
注意#xff1a;
一次可以移动多个点#xff0c;但是每个点只能移动一步。在同一次中#xf…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 vectorusing namespace std;int graph[20][20];
vectorint 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;queueStatus 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;
}
