搜索习题汇总
1. [USACO1.4] [IOI1994]时钟 The Clocks
题目描述
考虑将如此安排在一个 \(3 \times 3\) 行列中的九个时钟:
|-------| |-------| |-------|
| | | | | | |
|---o | |---o | | o |
| | | | | |
|-------| |-------| |-------|
A B C
|-------| |-------| |-------|
| | | | | |
| o | | o | | o |
| | | | | | | | |
|-------| |-------| |-------|
D E F
|-------| |-------| |-------|
| | | | | |
| o | | o---| | o |
| | | | | | | |
|-------| |-------| |-------|
G H I
目标要找一个最小的移动顺序将所有的指针指向 \(12\) 点。下面原表格列出了 \(9\) 种不同的旋转指针的方法，每一种方法都叫一次移动。
选择 \(1 \sim 9\) 号移动方法，将会使在表格中对应的时钟的指针顺时针旋转
\(90\) 度。
| 移动方法 | 受影响的时钟 |
|---|---|
| 1 | ABDE |
| 2 | ABC |
| 3 | BCEF |
| 4 | ADG |
| 5 | BDEFH |
| 6 | CFI |
| 7 | DEGH |
| 8 | GHI |
| 9 | EFHI |
例子：
9 9 12 9 12 12 9 12 12 12 12 12 12 12 12
6 6 6 5 -> 9 9 9 8 -> 9 9 9 4 -> 12 9 9 9 -> 12 12 12
6 3 6 6 6 6 9 9 9 12 9 9 12 12 12
但这可能不是正确的方法，请看下文。
输入格式
输入三行，每行三个正整数，表示一个时钟的初始时间，数字的含意和上面第一个例子一样。
输出格式
单独的一行包括一个用空格分开的将所有指针指向 \(12\) 点的最短移动顺序的列表。
如果有多种方案，输出那种使其连接起来的数字最小的方案。（举例来说 \(5\ 2\ 4\ 6 < 9\ 3\ 1\ 1\)）。
样例 #1
样例输入 #1
9 9 12
6 6 6
6 3 6
样例输出 #1
4 5 8 9
解题思路
1）本道题目复杂的地方在于需要同时考虑到九个时钟的状态，并且对时钟进行的操作都是离散的，数据的处理过程较为复杂。考察对搜索状态的存储及处理。
因此根据题意进行以下存储与操作的优化
- 时钟实际上只有四种状态，分别对应0、1、2、3，因此对于九个时钟，共计有410种状态，也就是220种状态。因此可以考虑以二进制的方式存储每种状态，每个时钟需要两位二进制。题目要求到达的最终状态，也就是所有时钟都指向12点，可以转换为所有时钟都对应0。
- 对于题目给出的九种操作，可以先通过数组的形式存储，方便后续搜索过程。
int choice[9][9] = {{1, 1, 0, 1, 1, 0, 0, 0, 0}, {1, 1, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 0, 1, 1, 0, 0, 0},
{1, 0, 0, 1, 0, 0, 1, 0, 0}, {0, 1, 0, 1, 1, 1, 1, 0, 0},{0, 0, 1, 0, 0, 1, 0, 0, 1},
{0, 0, 0, 1, 1, 0, 1, 1, 0}, {0, 0, 0, 0, 0, 0, 1, 1, 1}, {0, 0, 0, 0, 1, 1, 0, 1, 1}};
- 考虑到时钟存在 3 + 1 = 0回归原点的过程，思考利用加法器原理，运算时只考虑两位二进制，高位舍弃。同时对于某一状态，每次取一个时钟进行加法操作时，可通过右移对应位后&&3的方式来获取当前该时钟所对应的值。
- 题目要求输出最小次数操作对应的操作路径，因此可以开一个fa数组，下标为状态，对应的值记录到达当前状态所需要的上一操作序号。找到答案之后，沿着答案状态，向上遍历一遍过程，并用数组存储，最后倒序输出，即为最终的答案。
- 本题的目标是要求最小次数的过程，因此用BFS算法，每次将当前搜索的时钟状态入队列，扩展队列，直到找到最终状态，搜索结束。
代码
//TheClocks
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <math.h>
#include <queue>
using namespace std;
const int N = 1e7;
queue<int> q;
int op[N], fa[N], ans[N];
int choice[9][9] = {{1, 1, 0, 1, 1, 0, 0, 0, 0}, {1, 1, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 0, 1, 1, 0, 0, 0},
{1, 0, 0, 1, 0, 0, 1, 0, 0}, {0, 1, 0, 1, 1, 1, 0, 1, 0},{0, 0, 1, 0, 0, 1, 0, 0, 1},
{0, 0, 0, 1, 1, 0, 1, 1, 0}, {0, 0, 0, 0, 0, 0, 1, 1, 1}, {0, 0, 0, 0, 1, 1, 0, 1, 1}};
int main(){
int a = 0, temp, val = 0;
memset(fa, -1, sizeof(fa));
for(int i = 1; i <= 9; i++){
cin >> temp;
temp = temp / 3 % 4;
a += temp * pow(4, i-1);
}
q.push(a);
fa[a] = 0;
bool flag = 0;
while(!q.empty() && !flag){
int t = q.front();
q.pop();
for(int i = 1; i <= 9 && !flag; i++){
val = 0;
for(int j = 1; j <= 9; j++){
//status表示状态t下，当前第j个时钟的值
int status = (t >> ((j-1) * 2)) & 3;
//对第j个时钟，加上第i个操作中对应的值（0/1）
status = (status + choice[i-1][j-1]) & 3;
//加上当前status*权值
val += status << ((j-1) * 2);
}
//如果当前时钟状态未被访问到
if(fa[val] == -1){
q.push(val);
op[val] = i;
fa[val] = t;
if(val == 0) flag = 1;
}
}
}
int idx = 0;
val = 0;
while(val != a){
ans[++idx] = op[val];
val = fa[val];
}
for(int i = idx; i >= 1; i--) cout << ans[i] << " ";
cout << endl;
return 0;
}
题目相关知识点：除法的运算时间是乘法的4倍，乘法的运算时间是加法的7倍，加法的运算时间是位运算的十几倍，取模运算最慢。
除法能够转减法就转减法。
相关概念：快速乘除模
2. [USACO2.4] 回家 Bessie Come Home
题目描述
现在是晚餐时间，而母牛们在外面分散的牧场中。
Farmer John 按响了电铃，所以她们开始向谷仓走去。 你的工作是要指出哪只母牛会最先到达谷仓（在给出的测试数据中，总会有且只有一只最快的母牛）。在挤奶的时候（晚餐前），每只母牛都在她自己的牧场上，一些牧场上可能没有母牛。
每个牧场由一条条道路和一个或多个牧场连接（可能包括自己）。有时，两个牧场（可能是字母相同的）之间会有超过一条道路相连。至少有一个牧场和谷仓之间有道路连接。因此，所有的母牛最后都能到达谷仓，并且母牛总是走最短的路径。当然，母牛能向着任意一方向前进，并且她们以相同的速度前进。牧场被标记为 \(\texttt{a} \ldots \texttt{z}\) 和 \(\texttt{A} \ldots \texttt{Y}\)，在用大写字母表示的牧场中有一只母牛，小写字母中则没有。 谷仓的标记是 \(\texttt{Z}\)，注意没有母牛在谷仓中。
注意 \(\texttt{m}\) 和 \(\texttt{M}\) 不是同一个牧场。
输入格式
第一行一个整数 \(P\)（\(1\leq P \leq 10^4\)），表示连接牧场（谷仓）的道路的数目。
接下来 \(P\) 行，每行用空格分开的两个字母和一个正整数：被道路连接牧场的标号和道路的长度（道路长度均不超过 \(10^3\)）。
输出格式
单独的一行包含二个项目：最先到达谷仓的母牛所在的牧场的标号，和这只母牛走过的路径的长度。
样例 #1
样例输入 #1
5
A d 6
B d 3
C e 9
d Z 8
e Z 3
样例输出 #1
B 11
解题思路
从谷仓出发，用bfs搜索，每次扩展当前点。
易错点：对于已经入队列的点，仍存在着更优的路径。因此每次需要对当前改变的点的所有连接点for循环遍历一遍，若存在更优值则更新。
如图所示，假设当前点ABD已经入队列，点C值的更新会让点BD都更新。
代码
//come home
#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;
bool flag[60];
int p, a[60][60], min_val[60], fa[60], path[60];
int main(){
cin >> p;
char ch1, ch2;
int idx1, idx2;
int len;
for(int i = 1; i <= p; i++){
cin >> ch1 >> ch2 >> len;
//a~z分别对应1～26
if('a' <= ch1 && ch1 <= 'z') idx1 = ch1 - 'a' + 1;
//A~Z分别对应27～52
else idx1 = ch1 - 'A' + 27;
if('a' <= ch2 && ch2 <= 'z') idx2 = ch2 - 'a' + 1;
else idx2 = ch2 - 'A' + 27;
if(idx1 != idx2){
//如果当前两点不存在边
if(!a[idx1][idx2]) a[idx1][idx2] = a[idx2][idx1] = len;
//如果当前两点存在边
else if(a[idx1][idx2] > len) a[idx1][idx2] = a[idx2][idx1] = len;
}
}
queue<int> q;
q.push(52);
flag[52] = 1;
//对遍历到的点入队
while(!q.empty()){
int t = q.front();
q.pop();
for(int i = 1; i <= 52; i++){
//如果没有访问过当前结点
if(a[t][i] && !flag[i]){
q.push(i);
flag[i] = 1;
fa[i] = t;
min_val[i] = min_val[t] + a[t][i];
}
//判断对于点temp是否有更优的路径选择
else if(a[t][i]){
if(min_val[i] > min_val[t] + a[t][i]){
min_val[i] = min_val[t] + a[t][i];
fa[i] = t;
for(int j = 1; j <= 52; j++){
if(a[i][j] && min_val[j] > min_val[i] + a[i][j]){
min_val[j] = min_val[i] + a[i][j];
fa[j] = i;
}
}
}
}
}
}
int minn = 0x7f7f7f, end = 0;
for(int i = 27; i <= 51; i++){
if(min_val[i] != 0 && min_val[i] < minn){
minn = min_val[i];
end = i;
}
}
cout << char('A' + end - 27) << " " << minn << endl;
return 0;
}
3. meteor Shower S[USACO08FEB]
题目描述
贝茜听说一场特别的流星雨即将到来：这些流星会撞向地球，并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑，发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。
如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。
根据预报，一共有 \(M\) 颗流星 \((1\leq M\leq 50,000)\) 会坠落在农场上，其中第 \(i\) 颗流星会在时刻 \(T_i\)（\(0 \leq T _ i \leq 1000\)）砸在坐标为 \((X_i,Y_i)(0\leq X_i\leq 300\)，\(0\leq Y_i\leq 300)\) 的格子里。流星的力量会将它所在的格子，以及周围 \(4\) 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。
贝茜在时刻 \(0\) 开始行动，她只能在第一象限中，平行于坐标轴行动，每 \(1\) 个时刻中，她能移动到相邻的（一般是 \(4\) 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 \(t\) 被流星撞击或烧焦，那么贝茜只能在 \(t\) 之前的时刻在这个格子里出现。 贝茜一开始在 \((0,0)\)。
请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 \(−1\)。
输入格式
共 \(M+1\) 行，第 \(1\) 行输入一个整数 \(M\)，接下来的 \(M\) 行每行输入三个整数分别为 \(X_i, Y_i, T_i\)。
输出格式
贝茜到达安全地点所需的最短时间，如果不可能，则为 \(-1\)。
样例 #1
样例输入 #1
4
0 0 2
2 1 2
1 1 2
0 3 5
样例输出 #1
5
解题思路
本题求能够到达安全地方所使用的最短时间，安全地方指永远都不会有陨石落下来的地方。要求最短时间，所以考虑用bfs做，用队列存储当前到达的坐标的信息。
题目需要特殊处理的地方在于：
1）某一点不安全的时间取决于它自己以及上下左右四个点有陨石落下的最小值（除0之外），因此该点是否能经过，取决于最早到达该点时的时间是否小于最早陨石降落的时间；
2）题中没有限定只能在坐标300以内走，因此判断的时候要开大一点，如305，才能考虑到可以在外圈走的情况；
3）最后需要做特判，如果第0秒坐标原点就有陨石了，那么就game over了。
代码
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int t[310][310], t1[310][310], t_arr[310][310];
bool flag[310][310];
//上下左右四个方向
int dx[4] = {0 , 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
queue<pair<int, int>> q;
int main(){
int m, x, y;
//初始化陨石到达时间
for(int i = 0; i <= 305; i++){
for(int j = 0; j <= 305; j++) t[i][j] = 1005;
}
cin >> m;
for(int i = 1; i <= m; i++){
cin >> x >> y;
cin >> t[x][y];
}
//求当前位置陨石最早到达的时间，如果是安全地方，则t1为1005
for(int i = 0; i <= 305; i++){
for(int j = 0; j <= 305; j++){
t1[i][j] = min(t[i][j], t[i+1][j]);
t1[i][j] = min(t1[i][j], t[i][j+1]);
if(j-1 >= 0) t1[i][j] = min(t1[i][j], t[i][j-1]);
if(i-1 >= 0) t1[i][j] = min(t1[i][j], t[i-1][j]);
}
}
//特判
if(t1[0][0] == 0){
cout << 0 << endl;
return 0;
}
//bfs
q.push(make_pair(0,0));
t_arr[0][0] = 0;
flag[0][0] = 1;
while(!q.empty()){
pair<int, int> p1;
p1 = q.front();
int x = p1.first, y = p1.second;
q.pop();
//如果该坐标是安全的，则输出当前坐标的到达时间
if(t1[x][y] == 1005){
cout << t_arr[x][y] << endl;
return 0;
}
//超出范围，不入队，注意大于305
else if(x < 0 || y < 0 || x > 305 || y > 305 || t_arr[x][y] >= t1[x][y]) {
continue;
}
//向四个方向扩散,入队
for(int i = 0; i < 4; i++){
if(!flag[x+dx[i]][y+dy[i]]){
q.push(make_pair(x+dx[i], y+dy[i]));
flag[x+dx[i]][y+dy[i]] = 1;
t_arr[x+dx[i]][y+dy[i]] = t_arr[x][y] + 1;
}
}
}
cout << -1 << endl;
return 0;
}