A – 棋盘问题
题目：
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
思路：
这道题的题意不难理解，我们要求所有的摆放情况，对于这个问题，我们可以用dfs和bfs都可以，因为每一种可能的摆放都要尝试。
我们从头开始遍历，然后遇到一个符合的情况就尝试放进去，然后DFS，用vis数组记录每个点搜索的点，搜索到的点要做标记，表示这一行和这一列不再考虑其它的点。
代码还是很好理解的（尽管实现起来一直出bug）。
代码DFS：
#include<iostream>
#include<string.h>
using namespace std;
int mx[1005][1005];
int n,k;
int ans;
int vis[1005];
void dfs(int l,int step){
if(step == k){
ans++;
return ;
}
for(int i = l;i <= n;i++){
for(int j = 1;j <= n;j++){
//找到可以放的，并且没被占据
if(mx[i][j] == 1 && vis[j] == 0){
vis[j] = 1;
dfs(i + 1,step + 1);
vis[j] = 0;
}
}
}
}
int main(){
while(cin >> n >> k){
ans = 0;
memset(vis,0,sizeof(vis));
if(n == -1 && k == -1) break;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
char c;
cin >> c;
if(c == '.') mx[i][j] = 0;
else mx[i][j] = 1;
}
}
dfs(1,0);
cout << ans << "\n";
}
} B – Dungeon Master 地牢主
题目：
你被困在一个三维地牢中，需要找到最快的出路！这个地牢由单元立方体组成，这些立方体可能充满了岩石，也可能没有。你每移动一个单位向北、南、东、西、上或下需要一分钟。你不能对角移动，迷宫四面都被坚固的岩石所包围。
是否有可能逃脱？如果有，需要多长时间？
Input
输入包括多个地牢的描述。每个地牢的描述开始于一行，包含三个整数L、R和C（所有的数值都限制在30以内）。 L是构成地牢的层数。 R和C是构成每一层平面图的行数和列数。 然后会跟随L块R行每行C个字符。每个字符描述地牢的一个单元格。充满岩石的单元格用’#’表示，空单元格用’.’表示。你的起始位置用’S’表示，出口用字母’E’表示。每层后面有一个空行。输入以L、R和C三个零结束。
Output
每个迷宫生成一行输出。如果能够到达出口，打印一行形式如下的内容 Escaped in x minute(s)。
其中x被替换为逃脱所需的最短时间。 如果无法逃脱，打印行 Trapped!
思路：
这道题就是给一个三维的迷宫，然后从起始点走到终点。本质上来说，和二维地图的遍历没有什么区别，就是多了一维而已，开个三维数组就行。这道题因为是求最短时间，如果用DFS的话会把所有情况都考虑一遍，时间会很慢，很可能TLE，所以我们采用BFS来搜索。然后就是BFS的板子了，没有什么特别的，就是特判的时候注意一点。然后为了防止重复走，需要开个vis数组记录走过的地方（走迷宫不需要重复走）。然后结构体在函数里创建的时候是没有初始化的，所以需要自行初始化每一个变量。
代码BFS：
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
char mp[35][35][35];
int l,r,c;
typedef struct Node{
int x,y,z;
int step;
}node;
int s_x,s_y,s_z;
int e_x,e_y,e_z;
int flag;
int mv[6][3] = {{0,0,1},{0,0,-1},{1,0,0},{-1,0,0},{0,1,0},{0,-1,0}};
int vis[35][35][35];
void bfs(int x,int y,int z){
queue<node> q;
node start;
start.x = s_x;
start.y = s_y;
start.z = s_z;
start.step = 0;//一定要初始化
q.push(start);
while(!q.empty()){
start = q.front();
q.pop();
if(start.x == e_x && start.y == e_y && start.z == e_z){
flag = start.step;
return ;
}
//上下左右前后地走,拓展子节点
for(int i = 0;i < 6;i++){
node child;
child.x = start.x + mv[i][0];
child.y = start.y + mv[i][1];
child.z = start.z + mv[i][2];
//如果越界
if(child.x <= 0 || child.x > l || child.y <= 0 || child.y > r || child.z <= 0 || child.z > c){
continue;
}
//如果是墙壁
if(mp[child.x][child.y][child.z] == '#') continue;
//如果已经走过了
if(vis[child.x][child.y][child.z]) continue;
child.step = start.step + 1;
vis[child.x][child.y][child.z] = 1;
q.push(child);
}
}
}
int main(){
while(cin >> l >> r >> c){
if(l == 0 && r == 0 && c == 0) break;
memset(vis,0,sizeof(vis));
flag = 0;
for(int i = 1;i <= l;i++){
for(int j = 1;j <= r;j++){
for(int k = 1;k <= c;k++){
cin >> mp[i][j][k];
if(mp[i][j][k] == 'S'){
s_x = i,s_y = j,s_z = k;
}
if(mp[i][j][k] == 'E'){
e_x = i,e_y = j,e_z = k;
}
}
}
}
bfs(s_x,s_y,s_z);
if(flag){
cout << "Escaped in " << flag << " minute(s)." << "\n";
}else{
cout << "Trapped!" << "\n";
}
}
} C – Catch That Cow 抓住那头牛
题目：
农夫约翰得知了一头逃亡奶牛的位置，他想立即抓住她。他从数线上的点N（0 ≤ N ≤ 100,000）出发，而奶牛在同一数线上的点K（0 ≤ K ≤ 100,000）上。农夫约翰有两种交通方式：步行和传送。
- 步行：FJ可以在一分钟内从任何点X移动到点X – 1或X + 1
- 传送：FJ可以在一分钟内从任何点X移动到点2 × X
如果奶牛没有意识到被追赶并且根本不移动，那么农夫约翰需要多长时间才能抓到它？
Input
第1行：两个由空格分隔的整数：N和K
Output
第1行：农夫约翰抓到逃亡奶牛所需的最少时间，以分钟为单位。
思路：
这道题虽然乍一看不太像地图上的那种搜索，但是把数轴可以想成一个一维地图，转移方程就是X – 1、X + 1、2 × X。
这道题不能用DFS来解决，因为这样会陷入循环很难出来，就算用边界限制DFS的深度，每次也需要很长很长的时间。所以对于这种求最少时间、最短距离、最少步骤的题目，还是用BFS为好。代码也就是BFS的板子，没有什么不易于理解的。
代码BFS：
#include<iostream>
#include<queue>
using namespace std;
const int MAXN = 1000007;
int n,k;
int vis[MAXN];
typedef struct Node{
int n;
int step;
}node;
void bfs(int n){
queue<node> q;
node head;
head.n = n;
head.step = 0;
q.push(head);
while(!q.empty()){
head = q.front();
q.pop();
if(head.n == k){
cout << head.step << "\n";
return ;
}
for(int i = 1;i <= 3;i++){
node next;
if(i == 1) next.n = head.n + 1;
if(i == 2) next.n = head.n - 1;
if(i == 3) next.n = head.n * 2;
if(next.n < 0 || next.n > MAXN) continue;
if(!vis[next.n]){
vis[next.n] = 1;
next.step = head.step + 1;
q.push(next);
}
}
}
}
int main(){
cin >> n >> k;
bfs(n);
}D – Fliptile 翻转棋
题目：
农夫约翰知道，一个智力得到满足的奶牛是一头快乐的奶牛，快乐的奶牛会产出更多的奶。他为奶牛们安排了一项脑力活动，奶牛们要操作一个 M × N 的方格（1 ≤ M ≤ 15；1 ≤ N ≤ 15），每个方格的一面是黑色的，另一面是白色的。
正如人们所猜想的那样，当一个白色方格被翻转时，它会变成黑色；当一个黑色方格被翻转时，它会变成白色。当奶牛们翻转方格使得每个方格的白色面朝上时，它们就会得到奖励。然而，奶牛们的蹄子相当大，当它们尝试翻转一个特定的方格时，它们也会翻转所有相邻的方格（与被翻转的方格共享一条边的方格）。由于翻转很累人，奶牛们希望尽量减少它们需要做的翻转次数。
帮助奶牛们确定所需的最少翻转次数，以及为了达到这个最小值需要翻转的位置。如果有多种方法可以用最少的翻转次数完成任务，那么当作为字符串考虑时，返回字典序最小的一种。如果任务不可能完成，就打印一行，上面写着“IMPOSSIBLE”。
Input
第1行：两个用空格分隔的整数：M 和 N 第2行至第M+1行：第i+1行描述了网格第i行的颜色（从左到右），使用N个用空格分隔的整数表示，其中1代表黑色，0代表白色
Output
第1行至第M行：每行包含N个用空格分隔的整数，每个整数指定了需要翻转该特定位置的次数。
思路：
这道题如果我们把所有翻转的可能性都考虑一次的话，最多225个格子，每个格子有2种情况，就有2^225种可能，根本没办法做。所以我们没办法二维地枚举所有情况，我们就来观察一下方格盘。假设第一行的翻转情况固定，那我们现在要让第一行满足条件，就只能翻转第二行的，那现在翻转完之后，第二行的翻转情况也是固定的，我们就只能通过翻转第三行的格子，来让第二行满足条件，假设现在第三行也翻转完了，第二行也满足条件了，那为了让第三行也满足条件，我们就只能翻第四行的……一直到最后，为了让m – 1行满足条件，我们就只能翻转第m行的方格。最后m行能不能满足，完全取决于第一行方格的翻转情况。所以我们这道题只要穷举第一行的所有翻转情况就行，这样可能性就坍缩成了2^15种，是可以处理的。我们可以用DFS穷举第一行可能出现的所有翻转可能，然后从第二行到第m行我们按照刚才的思路模拟翻转就行了。
这道题是经典的状态压缩 + DFS + 模拟的题目，这里的DFS也可以用位运算来做。（虽然笔者还没学会）
以下的代码已经用注释写得很清楚了，还是比较容易看懂的。
代码DFS + 模拟：
#include<iostream>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
int vis[100];
int mx[100][100];//初始矩阵
int mp[100][100];//临时地图
int ans[100][100];//最终翻转次数
int temp[100][100];//临时翻转次数
int m,n;
int res = INF;
//模拟翻转
void flip(int i,int j){
mp[i][j] = !mp[i][j];
mp[i - 1][j] = !mp[i - 1][j];
mp[i][j - 1] = !mp[i][j - 1];
mp[i + 1][j] = !mp[i + 1][j];
mp[i][j + 1] = !mp[i][j + 1];
}
//对当前vis序列的情况开始模拟
void solve(){
//初始化临时翻转地图
memset(temp,0,sizeof(temp));
//先读入初始地图
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
mp[i][j] = mx[i][j];
}
}
//然后读入第一行的翻转，更新此时地图
for(int i = 1;i <= n;i++){
if(vis[i]){
//翻转第一行第i个
flip(1,i);
//记录翻转版本的地图
temp[1][i] = 1;
}
}
//接下来从第二行开始模拟，原则是：因为第一行的翻转情况已经固定，所以满足（上一行只能由下一行的翻转决定）
for(int i = 2;i <= m;i++){
for(int j = 1;j <= n;j++){
//如果上一行第j格需要翻转，就翻转
if(mp[i - 1][j]){
flip(i,j);
//翻转版本的地图别忘了记录
temp[i][j] = 1;
}
}
}
//接下来看看最后一行满不满足就行
for(int i = 1;i <= n;i++){
//不满足
if(mp[m][i]){
return ;
}
}
int cnt = 0;
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
if(temp[i][j]) cnt++;
}
}
//找到更小的，更新最终翻转版本地图
if(cnt < res){
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
ans[i][j] = temp[i][j];
}
}
res = cnt;
}
}
//dfs第一行的每一格的情况，从第一格到第m格，最后会把第一行的所有情况都出现一遍
void dfs(int x){
//第一行结束
if(x == n + 1){
solve();
return;
}
//记录第一行每个格子是0还是1
vis[x] = 0;
dfs(x + 1);
vis[x] = 1;
dfs(x + 1);
}
int main(){
cin >> m >> n;
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
cin >> mx[i][j];
}
}
dfs(1);
if(res == INF){
cout << "IMPOSSIBLE" << "\n";
}else{
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
cout << ans[i][j] << " ";
}
cout << "\n";
}
}
}E – Find The Multiple 查找倍数
题目：
给定一个正整数 n，编写一个程序来找出 n 的非零倍数 m，其十进制表示仅包含数字 0 和 1。您可以假设 n 不大于 200，并且有一个相应的 m 包含不超过 100 个十进制数字。
Input
输入文件可能包含多个测试用例。每行包含值 n （1 <= n <= 200）。包含零的行终止输入。
Output
对于输入中每个值 n 打印一行，其中包含相应的 m 值。m 的十进制表示形式不得超过 100 位。如果给定值 n 有多个解决方案，则其中任何一个都是可以接受的。
思路：
我们要找的是n的非零倍数m，但是m只能包含0和1，并且m可能很大。我们可以尝试穷举一下m所有的情况，但是深度要受限，比如在long long范围内的19位。所以这道题如果按照这个思路去写的话，代码还是很容易实现的。
代码DFS：
#include<iostream>
#include<cstring>
using namespace std;
int n;
long long m;
int flag;
void dfs(int len,long long x){
//假设dfs到了19位或者已经找到了
if(len > 19 || flag){
return ;
}
if(x % n == 0){
flag = 1;
cout << x << "\n";
return ;
}
dfs(len + 1,x * 10);
dfs(len + 1,x * 10 + 1);
}
int main(){
while(cin >> n){
if(!n) break;
dfs(1,1);
flag = 0;
}
}F – Prime Path 素数路径
题目：
内阁的部长们对安全部长的消息感到非常不安，消息称他们所有人都必须更改办公室的四位数房间号码。
- 出于安全考虑，每隔一段时间更改这些数字，以保持敌人的无知是很有必要的。
- 但是看，我选择我的号码1033是有充分理由的。你知道，我是首相！
- 我知道，因此你的新号码8179也是一个素数。你只需要把四个新数字贴在办公室门上的四个旧数字上。
- 不，这么简单。假设我把第一个数字改成8，那么数字就变成8033，这不是一个素数！
- 我明白了，作为首相，你不能忍受你的门上即使几秒钟也出现一个非素数。
- 正确！所以我必须设计一个方案，通过素数的路径从1033变到8179，每次只改变一个数字从一个素数变到下一个素数。
财政部长一直在偷听，这时他插了一句。
- 请不要进行不必要的开支！我刚好知道，一个数字的价格是一英镑。
- 嗯，在这种情况下，我需要一个计算机程序来最小化成本。你不会认识一些非常便宜的软件大师吧？
- 实际上我确实认识。你看，现在有一个编程比赛正在进行……帮助首相找到两个给定的四位素数之间最便宜的素数路径！第一个数字当然必须是非零的。以下是上述情况的一个解决方案。 1033 1733 3733 3739 3779 8779 8179 这个解决方案的成本是6英镑。请注意，第二步中贴过的数字1不能在最后一步重复使用——必须购买新的1。
Input
一行带有一个正数：测试案例的数量（最多100个）。然后对于每个测试案例，一行包含两个由空格分隔的数字。两个数字都是四位素数（没有前导零）。
Output
每个案例一行，要么是一个表示最小成本的数字，要么包含单词Impossible。
思路：
这道题要找最少步数，所以马上就想到了用BFS去跑。模拟一遍更换数位的操作，然后用step数组来记录步数，用vis数组来记录访问过的，不然会重复访问的。数据量也不大，四位数的素数总计1061个，还是能跑完的，也不用写素数筛，直接用朴素的判断法就行。最坏情况是所有四位的素数都找到一遍，其实不可能出现找不到的情况。
代码BFS：
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
int a,b;
int ans = INF;
int vis[10000];
int step[10000];
int judge(int n){
if(n == 1) return false;
if(!(n & 1)) return false;
for(int i = 2;i * i <= n;i++){
if(n % i == 0) return false;
}
return true;
}
int bfs(){
memset(vis,0,sizeof(vis));
memset(step,0,sizeof(step));
queue<int> q;
int node = a;
q.push(node);
vis[node] = 1;
step[node] = 0;
ans = INF;
int cnt = 0;
while(!q.empty()){
node = q.front();
q.pop();
if(node == b){
ans = min(ans,step[node]);
return ans;
}
for(int i = 1;i <= 4;i++){
for(int j = 0;j <= 9;j++){
if(i == 1 && j == 0) continue;
int thou = node / 1000;
int hand = (node - 1000 * thou) / 100;
int shi = (node - (node / 100) * 100) / 10;
int ge = node % 10;
if(i == 1){
thou = j;
}else if(i == 2){
hand = j;
}else if(i == 3){
shi = j;
}else if(i == 4){
ge = j;
}
int next = thou * 1000 + hand * 100 + shi * 10 + ge * 1;
if(!judge(next) || vis[next] || next <= 1000){
continue;
}
vis[next] = 1;
step[next] = step[node] + 1;
q.push(next);
}
}
}
}
int main(){
int t;
cin >> t;
while(t--){
cin >> a >> b;
bfs();
if(ans != INF)
cout << ans << "\n";
else cout << "IMPOSSIBLE\n";
}
}G – Shuffle’m Up
题目：
在扑克桌上，德州扑克玩家常常会进行一种消遣活动，那就是洗牌筹码。洗牌筹码的方式是通过使用两堆扑克筹码S1和S2，每堆筹码包含C个筹码。每堆筹码可能包含多种不同颜色的筹码。
实际的洗牌操作是通过将来自S1的一个筹码与来自S2的一个筹码交错排列，如下所示，对于C = 5：
最终的堆栈S12包含2 * C个筹码。S12的底部筹码是来自S2的底部筹码。在该筹码上方是来自S1的底部筹码。交错过程继续，从S2底部取出第二个筹码放在S12上，然后是从S1底部取出的第二个筹码，依此类推，直到将来自S1的顶部筹码放在S12的顶部。
洗牌操作后，通过从S12底部取出底部的C个筹码形成新的S1，从S12顶部取出顶部的C个筹码形成新的S2，将S12分割成两个新堆栈。然后可以重复洗牌操作以形成新的S12。
要解决这个问题，您需要编写一个程序来确定是否可以通过对两个堆栈进行若干次洗牌来形成特定的结果堆栈S12。
Input
输入的第一行包含一个整数N，表示接下来的数据集数量（1 ≤ N ≤ 1000）。
每个数据集包括四行输入。数据集的第一行指定一个整数C（1 ≤ C ≤ 100），表示每个初始堆栈（S1和S2）中的筹码数量。每个数据集的第二行指定堆栈S1中每个筹码的颜色，从底部筹码开始。每个数据集的第三行指定堆栈S2中每个筹码的颜色，同样从底部筹码开始。颜色用单个大写字母（A到H）表示。在筹码颜色之间没有空格或分隔符。每个数据集的第四行包含2 * C个大写字母（A到H），表示对S1和S2进行零次或多次洗牌后所期望的结果的颜色。底部筹码的颜色首先给出。
Output
对于每个数据集，输出一行，显示数据集编号（1到N），然后是一个整数值，表示获得期望的结果堆栈所需的最小洗牌次数。如果使用数据集的输入无法达到期望的结果，则输出洗牌次数的值为-1。
思路：
这道题的题意大致就是，给定两个字符串s1和s2，然后通过题目要求的“洗牌”操作变成字符串s12就可以了，输出操作的次数。这道题其实直接模拟就好了，感觉也不需要特地写个搜索。如果一定要写个搜索的话，其实本质也就是模拟，只是代码看起来简略了很多。我们需要有一个判断条件，判断什么时候洗牌无法达到预期效果。我们会观察到，每次洗牌做的操作都是一模一样的，只由字符串本身决定下一次洗出什么样的字符串。所以如果一个字符串在洗牌过程中重复出现，说明此时一定进入死循环了，所以这个时候输出-1即可。如果没遇到死循环，那就一直继续运行，直到得到字符串s12为止。
代码DFS：
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
int cc;
int n;
string s1,s2,s12;
int flag,ans;
map<string,int> mp;
void dfs(string a,string b,string c){
ans++;
string res = "";
for(int i = 0;i < cc;i++){
res += b[i];
res += a[i];
}
mp[res]++;
//重复出现
if(mp[res] > 1){
flag = 1;
return ;
}
//找到结果
if(res == c){
return ;
}
//继续模拟
for(int i = 0;i < cc;i++){
a[i] = res[i];
b[i] = res[cc + i];
}
dfs(a,b,c);
}
int main(){
cin >> n;
int t = 0;
while(n--){
t++;
flag = 0;
cin >> cc;
cin >> s1 >> s2;
cin >> s12;
mp.clear();
ans = 0;
dfs(s1,s2,s12);
if(flag) ans = -1;
cout << t << " " << ans << "\n";
}
}H – Pots 花盆
题目：
给定两个容量分别为A升和B升的罐子。可以执行以下操作：
- FILL(i)：从水龙头向罐子i（1 ≤ i ≤ 2）注满水；
- DROP(i)：将罐子i倒空到排水口；
- POUR(i, j)：从罐子i向罐子j倒水；执行此操作后，罐子j可能已经满了（罐子i中可能还有一些水），或者罐子i已经空了（所有内容都已经移至罐子j）。
编写一个程序，找到能够得到恰好C升水的最短操作序列，操作序列可以是上述操作的组合。
Input
第一行包含三个整数A、B和C。这些整数都在1到100的范围内，且C≤max(A,B)。
Output
输出的第一行必须包含操作序列的长度K。接下来的K行必须描述每个操作。如果有多个最短长度的操作序列，请输出其中任意一个。如果无法达到所需结果，则文件的第一行必须包含单词’impossible’。
思路：
一眼看到最短操作序列，就知道肯定要用BFS做，因为如果用DFS搜索的话，甚至可能出现根本搜索不到答案的情况。我们可以枚举一下可能会有哪些操作：{“FILL(1)”,”FILL(2)”,”DROP(1)”,”DROP(2)”,”POUR(1,2)”,”POUR(2,1)”}。然后我们用BFS考虑各种情况就可以，理论存在，实践开始！除了输出的代码需要仔细想一想以外，基本上还是BFS的影子。具体细节看下方代码，还是比较简单易懂的。
代码BFS：
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
int a,b,c;
string mv[] = {"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
//定义两桶状态的数据结构
typedef struct node{
int a,b;//定义状态
int step;//定义步数
vector<string> op;//存储操作
}node;
int vis[1000][1000];
void bfs(){
queue<node> q;
q.push({0,0,0});
while(!q.empty()){
node head = q.front();
q.pop();
//判断是否满足条件，满足条件就结束
if(head.a == c || head.b == c){
cout << head.step << "\n";
int len = head.op.size();
for(int i = 0;i < head.step;i++){
cout << head.op[i] << "\n";
}
return ;
}
//开始搜索
for(int i = 0;i < 6;i++){
int aa = head.a;
int bb = head.b;
if(i == 0){
aa = a;
}
if(i == 1){
bb = b;
}
if(i == 2){
aa = 0;
}
if(i == 3){
bb = 0;
}
if(i == 4){
aa = max(head.a - (b - head.b),0);
bb = min(b,head.b + head.a);
}
if(i == 5){
bb = max(head.b - (a - head.a),0);
aa = min(a,head.a + head.b);
}
//访问过的状态
if(vis[aa][bb]) continue;
vis[aa][bb] = 1;
node temp;
temp.a = aa,temp.b = bb,temp.step = head.step + 1;
temp.op = head.op;
temp.op.push_back(mv[i]);
q.push(temp);
}
}
cout << "impossible" << "\n";
}
int main(){
cin >> a >> b >> c;
bfs();
}I – Fire! 火！
题目：
Joe在一个迷宫中工作。不幸的是，迷宫的某些部分起火了，迷宫的所有者忽视了制定防火逃生计划。帮助Joe逃离迷宫。 给定Joe在迷宫中的位置以及迷宫中哪些方块着火，您必须确定Joe是否能在火势到达之前逃出迷宫，以及他可以多快做到。 Joe和火每分钟移动一个方块，垂直或水平移动（不是对角线移动）。火从每个着火的方块向四个方向蔓延。Joe可以从与迷宫边缘相邻的任何方块逃离迷宫。Joe和火都不能进入墙壁上的方块。
Input
输入的第一行包含一个整数，表示接下来的测试用例数。每个测试用例的第一行包含两个整数R和C，用空格分隔，其中1≤R，C≤1000。测试用例的接下来的R行每行包含迷宫的一行。每行包含恰好C个字符，每个字符为以下之一：
• #，墙
• .，可通过的方块
• J，Joe在迷宫中的初始位置，为可通过的方块
• F，着火的方块 每个测试用例中将恰好有一个J。
Output
对于每个测试用例，如果Joe在火到达之前无法逃出迷宫，则输出一行包含“IMPOSSIBLE”，否则输出一个整数，表示Joe可以安全地在多少分钟内逃出迷宫。
思路：
这道题就是有个迷宫，有人和火，人到达迷宫边缘就算成功。和普通的BFS的区别在于，这里有很多的火，从一开始就要把火都推入队列。其次有另一个问题，就是我们处理的对象有两个，一个是人和火。一个简单的思路就是先对火进行BFS，记录每个格子会着火的时间点，如果人可以在这个格子的着火时间之前到达，就可以走这个格子，否则不可以走，最后能到达边缘就算胜利。但是也可以采用笔者这种写法，把火和人同时进行BFS，开个结构体，用一个flag状态作为区分，然后每一秒也是火走一下，人走一下，省去了记录着火时间的事情，最后看看人能不能到达边缘。其实两种思维没什么区别，但是只写一个BFS感觉会轻松一点。
代码BFS：
#include<bits/stdc++.h>
using namespace std;
char mx[1005][1005];
char vis[1005][1005];
int mv[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int r,c;
int s_x,s_y;
//定义地图每个点的状态
typedef struct node{
//坐标
int x,y;
//步数
int step;
//状态，1为火
int flag;
}node;
queue<node> q;
int ans = -1;
void bfs(){
//把人推入队列
q.push({s_x,s_y,0,0});
while(!q.empty()){
node head = q.front();
q.pop();
//人满足逃离的条件
if(head.flag == 0 && (head.x == 1 || head.y == 1 || head.x == r || head.y == c)){
ans = head.step + 1;
return ;
}
for(int i = 0;i < 4;i++){
int xx = head.x + mv[i][0];
int yy = head.y + mv[i][1];
if(xx >= 1 && yy >= 1 && xx <= r && yy <= c && mx[xx][yy] != '#' && !vis[xx][yy]){
vis[xx][yy] = 1;//走过的不再走
node next;
next.x = xx,next.y = yy,next.step = head.step + 1,next.flag = head.flag;
q.push(next);
}
}
}
}
int main(){
int t;
cin >> t;
while(t--){
ans = -1;
cin >> r >> c;
//清空队列
while(!q.empty()){
q.pop();
}
memset(vis,0,sizeof(vis));
//读入地图，并且读入火的位置和人的起始位置
for(int i = 1;i <= r;i++){
for(int j = 1;j <= c;j++){
cin >> mx[i][j];
if(mx[i][j] == 'J'){
s_x = i,s_y = j;
}
if(mx[i][j] == 'F'){
//把火推入队列
q.push({i,j,0,1});
}
}
}
bfs();
if(ans == -1){
cout << "IMPOSSIBLE\n";
}else{
cout << ans << "\n";
}
}
}J – 迷宫问题
题目：
定义一个二维数组：int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input 输入
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output 输出
左上角到右下角的最短路径，格式如样例所示。
思路：
找迷宫的最短路线，一眼就能看出是一个很简单的BFS啦，除了记录路径这个事情需要思考一下，直接上代码，没什么好多说的。
代码BFS：
#include<iostream>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
int mx[105][105];
int mv[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
int vis[105][105];
typedef struct node{
int x,y;
int step;
vector<pair<int,int> > pre;
}node;
void bfs(){
node head;
head.x = 0,head.y = 0;
head.step = 0;
head.pre.clear();
queue<node> q;
q.push(head);
while(!q.empty()){
head = q.front();
q.pop();
if(head.x == 4 && head.y == 4){
head.pre.push_back(make_pair(4,4));
for(int i = 0;i <= head.step;i++){
cout << "(" << head.pre[i].first << ", " << head.pre[i].second << ")\n";
}
return ;
}
for(int i = 0;i < 4;i++){
int xx = head.x + mv[i][0];
int yy = head.y + mv[i][1];
if(xx < 0 || yy < 0 || xx > 4 || yy > 4 || mx[xx][yy] == 1){
continue;
}
if(!vis[xx][yy]){
vis[xx][yy] = 1;
node next;
next.x = xx,next.y = yy,next.step = head.step + 1,next.pre = head.pre;
next.pre.push_back(make_pair(head.x,head.y));
q.push(next);
}
}
}
}
int main(){
for(int i = 0;i < 5;i++){
for(int j = 0;j < 5;j++){
cin >> mx[i][j];
}
}
bfs();
}总结
这套题的DFS和BFS都很有意思，难度适中，能学到很多东西，并且熟悉很多题型。
- 最短路径，最少步数这种题目还是优先BFS
- 很多题目虽然套了搜索的皮，但其实很需要模拟的功底
- 记录走过的路径也是很常见的题目，笔者最喜欢的写法就是开个结构体，然后再开个vector数组记录路径
- 像D题的状态压缩这种题目比较难写，这种题目可以作为笔记存留
- 基本上DFS和BFS的题目的精髓就在于两部分：怎么定义状态 + 怎么移动【怎么找到下一个节点或者说状态转移】