绕了两个大圈，终于是到了正题了，今天我们就来学一学它！全是干货！
搜索
假设你此时身处一个很大很大的迷宫中，你什么都不知道，只知道这个迷宫有一个出口，迷宫中每一个格子有很多条路和其他格子相连。而你要做的就是走到这个出口去，假设你有足够的水和食物保证你能生存下来。那么你需要设计一个策略保证你一定能走出去。
首先，如果你在迷宫中到处乱闯，就算你有足够的水和食物，但是你有很大可能陷入一个死循环，一直在打转，永远也走不出去。
因为你对迷宫信息毫不知情，那么如果要保证你一定可以走出迷宫，那么只有一种可能——当你把整个迷宫都走遍了。
那么，现在你就需要思考：
（1）如果我不想走回头路，应该如何设计策略？
（2）为了让你的行程看上去不杂乱，你每次走到下一个位置应该选择什么策略？
（3）你怎么才知道迷宫中的哪些位置你走过，哪些位置你没有走过？
(1)如果我不想走回头路，应该如何设计策略？
当我们从一个位置走到下一个位置的时候，那么此时我们有两种选择。第一种是回到上一个位置，第二种是继续往下面走。如果我们不想走回头路，那么我们的策略就应该是一直往后面走，直到走到死路位置。
（2）为了让你的行程看上去不杂乱，你每次走到下一个位置应该选择什么策略？
每一个位置面前都有几条路可以选择，为了让行程不杂乱，我们可以按照自己给定点的顺序给这些道路编一个号，每次都按顺序走这些道路。
（3）你怎么才知道迷宫中的哪些位置你走过，哪些位置你没有走过？
这个很容易想到，在每一个位置做一个标记，在代码中表现为book[i]=1.如果走到一个位置，这个位置有标记说明我们走过了。
如果这个位置所有路口都走过了，我们应该怎么办呢？返回上一个位置，换一条路继续往下走。
前面的这种策略叫做一种搜索策略，准确的说叫深度优先搜索策略，即先朝着一个方向一直搜索下去。我们把这种策略转换成程序来实现。
为了方便，我们可以先把迷宫看做n*m的方格，每次只能上下左右走。
那么题意可以转换为：你处于方格中的一个位置，问你是否可以走到某一个特定的位置(出口)
那么：
（1）怎么实现行走路线？
（2）怎么实现哪些位置被走过？
对于方格中的任意一点，可以往上下左右走。
我们可以自己定义一个行走顺序，比如上，右，下，左，那么用数字代替就是0,1,2,3
每一个位置的上下左右和该点坐标都有关系，我们可以用坐标偏移量来表示，从该点出发第0条路的坐标偏移量就是(-1,0),第1条路就是(0,1),第2条路就是(1,0),第3条路就是(0,-1)。
我们可以开一个数组来存储nextn[4][2]={-1,0,0,1,1,0,0,-1}
（1）如果从一个点可以走到上下左右，左上，右上，左下，右下八个点，坐标偏移数组应该如何写？
int dr[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
（2）如果从一个点可以走到横坐标翻倍，纵坐标翻倍，横坐标减半，纵坐标减半的四个位置，坐标偏移量应该如何写？
double dr[4][2]={{1,2},{2,1},{0.5,1},{1,0.5}};
x=x*dr[k][0],y=y*dr[k][1];
next[4][2]={-1,0,0,1,1,0,0,-1}
next[i][0]:表示从该点出发第i条路的x坐标偏移量
next[i][1]:表示从该点出发第i条路的y坐标偏移量
那么如果该点坐标是(x,y)，那么下一个点的坐标就是(x+next[i][0],y+next[i][1])
但是我们要注意，对于迷宫中最外层的点，并不是上下左右都可以走的，因为迷宫是有限大的，所以我们需要判断一下，对于x坐标，如果x<1||x>n,对于y坐标，如果y<1||y>m,那么这些点在迷宫中实际上是不存在的，所以不能走。
前面我们是直接标记book[i]=1就可以了，但是在标记的时候一定要注意没有歧义，我们每走到一个点，就给这个点标一个递增的号码，那么号码是不会重复的，所以不会有歧义。但是在方格中，无论用行标还是列标来标记都会有歧义，所以我们可以用二维坐标或者按照行一直标号下去((x-1)*m+y),虽然都没有问题，但是我们还要考虑坐标偏移量，所以用二维坐标(x,y)好一些，那么标记就变成了book[x][y]，表示(x,y)这个位置被访问过了。
深搜模板
used[x][y]=1;
void dfs(int x,int y){
if (x>n||x<1||y>m||y<1)return;
if (x==X&&y==Y){
...
}
for (int i=0;i<4;i++){
int rx=x+dr[i][0],ry=y+dr[i][1];
if (used[rx][ry]==0){
used[rx][ry]=1;
dfs(rx,ry);
used[rx][ry]=0;
}
}
return;
}
当然，我们都知道对于方阵来说，从任意一个点肯定可以到达任意一个点。所以我们加入障碍物，障碍物表示该位置不可以走。
其他地方都不变，只是可不可以走的地方还需要加一个判断语句，为了区分哪些点可以走，哪些点不可以走，我们可以加入一个map数组，map[x][y]=1表示该点是障碍物，不可以走，map[x][y]=0表示可以走。
if (used[rx][ry]==0&&map[rx][ry]==0){
used[rx][ry]=1;
dfs(rx,ry);
used[rx][ry]=0;
}
深搜求最短路
前面是深搜的模型，但是很多时候都不是判断从一个点是否可以到达另一个点，而是求从一个点到达另一个点的最短路。
按照前面的做法，我们可以得到从起点到终点的一条路径，但是这条路径是否是最短的路径我们是不知道的，我们要如何才能保证我们得到的一定是从起点到终点的最短路径呢？
当我们用深度优先搜索尝试所有可能情况的时候，如果搜到终点之后返回继续搜索，看是否还有其他路径可以到达终点，那么最终会得到从起点到终点所有的可能路径，其中最短的那一条就是最短路径。
我们要知道起点到终点的路径长度，那么就需要实时记录当前路径长度，这样才能在找到终点的时候马上得到长度，所以我们在传递参数的时候不仅要传递坐标，还需要传递当前路径长度。
同样，由于当我们到达终点后还需要返回继续寻找其他路径，以及之前找的某一条路径可能无法到达终点，所以我们在搜索的时候还需要一个回溯的过程，即搜索完之后返回上一层之前取消掉该点的标记。
最后，当到达终点后，如果答案比之前的最小值还要小，那么就更新答案，否则答案不变。
used[x][y]=1;
void dfs(int x,int y,int step){
if (x>n||x<1||y>m||y<1)return;
if (x==X&&y==Y){
minn=min(step,minn);
return;
}
for (int i=0;i<4;i++){
int rx=x+dr[i][0],ry=y+dr[i][1];
if (used[rx][ry]==0&&a[rx][ry]==0){
used[rx][ry]=1;
dfs(rx,ry,step+1);
used[rx][ry]=0;
}
}
return;
}
深搜的优化和最优性剪枝
这样做方法是没有问题的，但是实践起来会发现效率太低，因为可能的路径太多了，所以我们需要优化，也就是排除掉不可能是最短路的路径。
（1）有重复的路径肯定不是最短路。
（2）前面我们是走到终点再判断和前面求出来的最短路的大小关系，但是实际上因为路径都是正数，所以只要在中途，路径长度>=前面求出来的最短路，那么实际上就没有必要搜索下去了。肯定不是最短路,例如下图，搜索到5号结点就没必要继续搜索下去了。
if (step>minn)return;
if (x==X&&y==Y){
minn=min(step,minn);
return;
}
对于一条最短路径而言，如果要整条路径是最短路径，那么其中任意一个点到起点的路径都应该最短，否则他就不是最短路径。
在已知的搜索路径中，起点到某一点的最短路径为m1，如果其他路径中起点到该点的距离L>m1，也不需要再往下搜索了，因为这条路径肯定不可能是最短路径，效率得到了大大的提高。
所以我们需要开一个二维数组dis[i][j]表示点(i,j)到起点的最短距离，当到达该点时，比较当前长度l和dis[i][j]的大小关系:
如果l<dis[i][j]，那么说明可以继续搜索下去，同时不要忘记更新dis[i][j]的值为l。
如果l>=dis[i][j],说明之前已经搜索到一条更短的路径，这条路径一定不是最短路径，就不需要继续往下搜索了，提前返回。
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
dis[i][j]=INT_MAX;
}
}
if (step>dis[x][y])return;
dis[x][y];
基础知识基本上都带完了，现在就来看例题把
求细胞数量
题目描述
一矩形阵列由数字 0 0 0 到 9 9 9 组成，数字 1 1 1 到 9 9 9 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。
输入格式
第一行两个整数代表矩阵大小 n n n 和 m m m。
接下来 n n n 行，每行一个长度为 m m m 的只含字符 0 到 9 的字符串，代表这个 n × m n \times m n×m 的矩阵。
输出格式
一行一个整数代表细胞个数。
样例 #1
样例输入 #1
4 10
0234500067
1034560500
2045600671
0000000089
样例输出 #1
4
提示
数据规模与约定
对于 100 % 100\% 100% 的数据，保证 1 ≤ n , m ≤ 100 1 \le n,m \le 100 1≤n,m≤100。
从一个点出发能够到达的所有点是一个细胞，我们把经过的点标记，注意这里不回溯，每个点被标记一次。
因为从任意一个点出发都有可能是一个新的细胞，所以我们枚举矩阵中的每一个点，如果已经被标记过，那么说明是之前找到的一个细胞上的点，已经计算过了，不需要再计算。如果改变没有标记，那么说明该点所在的细胞还没有被遍历，继续按照之前的方式去遍历它，同时也说明多了一个新的细胞，计数器+1
//当初作者使用广度写的，所以就用了我同学的代码，码风可能有点不一样
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,a[1010][1010],nextn[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
char c;
bool book[1010][1010];
void f(int x,int y)
{
for(int k=0;k<4;k++)
{
int a1=x+nextn[k][0],b1=y+nextn[k][1];
if(a[a1][b1]!=0&&book[a1][b1]==0)
{
book[a1][b1]=1;
f(a1,b1);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>c;
a[i][j]=c-'0';
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]!=0&&book[i][j]==0)
{
f(i,j);
cnt++;
}
}
}
cout<<cnt;
return 0;
}
最短路的具体路径
上面我们学习了如何用深搜求解最短路径以及提高深搜效率的剪枝。
但是在实际操作中可能不仅仅会询问最短路径的长度，还可能会询问最短路的条数以及最短路的具体路径（任意一条），对于这两种情况，应该如何求解呢？
当搜索到终点的时候，就表示一种到达终点的方案，但是当前答案和之前的最小值之间存在三种情况：
（1）l>Min,当前路径不是最短路，会被提前剪枝掉，不予考虑。
（2）l=Min,当前路径和目前的最短路相同，说明最短路的数量多了一条，所以cnt++。
（3）l<Min,当前路径比之前所有路劲长度都要短，那么之前所有路径都不是最短路，当前路径才是最短路，所以cnt=1。
void dfs(int x,int y,int step)
{
if(step>Min)//剪枝
return ;
if(到达终点)
{
if(step==Min)//假设当前最小值就是最优值，存在一条和他一样优的结果，方案+1
方案数+1;
else//前面的最小值不是最优值，说明前面的方案都不符合条件，只有当前方案最优
方案数=1;
}
}
如果我们要知道最短路的具体路径，就需要知道这条路径上的每一个点的上一个点或者下一个点是哪一个点，这样就能顺藤摸瓜从起点找到终点或者从终点找到起点。
那么到底是记录每个点的上一个点还是下一个点呢？对于每一个点，他能够到达的点最多有4个，如果记录下一个点需要4个点都记录，因为任何一个点都有可能是最短路径上的点。而且从起点出发的点虽然一定经过起点，但是不一定能够到达终点，所以记录每一个点的下一个点的方式比较麻烦，还不容易正确
如果记录每个点的上一个点，虽然一个点可以由四个点到达，但是由于是最短路径上的点，所以路径上的任意一个点到起点的路径都必须是最短的，所以在到达该点时，判断一下从哪个点过来路径长度最短，就把该点的上一个点更新为这个点。因为记录的是上一个点的位置，所以我们需要从终点开始往回找，对于到达终点的路径，他一定是会经过起点的。
其实这就是前驱
对于每一个点，需要记录上一个点的坐标，所以每个点需要开一个结构体，分别记录上一个点的横、纵坐标以及当前最短路径长度。
struct Node{
int fx,fy;
int minstep;
};
同时，对于当前点(x,y)，我们还需要知道他的上一个点坐标，所以在递归传递参数时，还需要把当前点的坐标传递下去。
void dfs(int fx,int fy,int x,int y,int step){
dfs(x,y,tx,ty,step+1);
}
当我们记录好最短路径上的每一个点的前驱后，那么如何找到这一条路径呢？
因为记录的是前驱，所以找的时候要从终点往起点查找。因为路径上的点不确定，所以我们需要用while循环。终止条件为找到起点即为结束，路径上任何一个点都有前驱，除了起点（起点前驱为0），所以终止条件可以写成如果到达起点或者当前点的前驱为0。
因为路径不止一条，所以一般会先给定搜索的方式或者用special judge。
记忆化搜索
在学习递归的时候，我们就学习过记忆化，这是能大幅度提高递归的一种方法，同样，在一些搜索题目中，也可以考虑记忆化。
但是要注意记忆化搜索不是每道搜索题中都可以用到的，记忆化的前提是前后两段一定不会有重叠部分。
比如从起点搜到(x,y)，如果之前从点(x,y)搜索到过终点，在返回的时候在点(x,y)的位置记录了答案，这种情况无法使用记忆化搜索，因为不能保证这两段路径没有重叠。
简单来说，普通的搜索题不能随意使用记忆化搜索，除非保证该点之前的路径和该点之后的路劲不会有重叠。
上例题！
[SHOI2002] 滑雪
题目描述
Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 24 − 17 − 16 − 1 24-17-16-1 24−17−16−1（从 24 24 24 开始，在 1 1 1 结束）。当然 25 25 25－ 24 24 24－ 23 23 23－ … \ldots …－ 3 3 3－ 2 2 2－ 1 1 1 更长。事实上，这是最长的一条。
输入格式
输入的第一行为表示区域的二维数组的行数 R R R 和列数 C C C。下面是 R R R 行，每行有 C C C 个数，代表高度(两个数字之间用 1 1 1 个空格间隔)。
输出格式
输出区域中最长滑坡的长度。
样例 #1
样例输入 #1
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
样例输出 #1
25
提示
对于 100 % 100\% 100% 的数据， 1 ≤ R , C ≤ 100 1\leq R,C\leq 100 1≤R,C≤100。
从任何一个点作为起点往下滑都有可能是最长的路径。所以需要枚举起点，从起点开始执行搜索，但是这样做肯定会超时。
我们思考，从A点到达终点B点，途中经过了X点，那么X点到A点和B点的距离都是最长的，也就是说我们是知道X点到终点B点的最长路径的，当下次枚举点X作为起点的时候，就不需要再去搜索一遍了。而且由于高只能下降，那么AX的路径和XB的路径肯定不会有重叠部分，那么该题就可以考虑用记忆化搜索，在返回每个点时，记录终点到该点的最长路径，这样被搜索过的点只会被搜索一次。
该题是求最长路径，所以是无法用最优性剪枝的，只有求最小值的情况次可以用最优性剪枝，所以不需要再开之前的dis数组。
那么我们这里开一个dis数组dis[x][y]表示以(x,y)作为起点的最长路径长度。
对于每一个点，当他的上下左右四个点都搜索完之后返回该点的时候，那么就可以得到从该点出发的最长路径，并且把这个答案记录下来返回给调用他的点。
因为该题高度会一直下降，同一个点不会被走多次，所以也不需要标记数组。
（1）如果该点之前被搜索过，那么直接返回。
（2）因为没有终点，所以会把从起点开始能到达的所有点都搜索完，当返回时，返回值的最大值就是当前点的答案。
（3）得到该点的最长路径后，保存答案并把答案作为返回值返回。
#include<bits/stdc++.h>
#include<queue>
using namespace std;
int n,m;
int dx[4] = {0,1,-1,0};
int dy[4] = {1,0,0,-1};
int a[2100][2100];
int f[2100][2100];
int ct;
inline int read(){
int x=0;
char ch=0;
while (ch<'0'||ch>'9')ch=getchar();
while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return ch;
}//手痒了
int dfs(int x,int y){
if(f[x][y]!=0) return f[x][y];
++ct;
f[x][y] = 1;
for(int i = 0;i < 4;i++){
int xx = dx[i] + x;
int yy = dy[i] + y;
if(xx <1 || xx>n||yy < 1||yy >m|| a[xx][yy] >= a[x][y]){
continue;
}
dfs(xx,yy);
f[x][y] = max(f[x][y],f[xx][yy] + 1);
}
return f[x][y];
}
int main() {
cin >> n >> m;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
scanf("%d",&a[i][j]);//忘记用了
}
}
int ans = 0;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
ans = max(ans,dfs(i,j));
}
}
cout <<ans;
return 0;
}
[NOIP2017 普及组] 棋盘
题目背景
NOIP2017 普及组 T3
题目描述
有一个 m × m m \times m m×m 的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。
任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 $1 $ 个金币。
另外， 你可以花费 2 2 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。
现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？
输入格式
第一行包含两个正整数 $ m, n$，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。
接下来的 $ n $ 行，每行三个正整数 $ x, y, c$， 分别表示坐标为 ( x , y ) (x,y) (x,y) 的格子有颜色 $ c$。
其中 $ c=1$ 代表黄色，$ c=0$ 代表红色。 相邻两个数之间用一个空格隔开。 棋盘左上角的坐标为 ( 1 , 1 ) (1, 1) (1,1)，右下角的坐标为 ( m , m ) ( m, m) (m,m)。
棋盘上其余的格子都是无色。保证棋盘的左上角，也就是 ( 1 , 1 ) (1, 1) (1,1) 一定是有颜色的。
输出格式
一个整数，表示花费的金币的最小值，如果无法到达，输出 -1。
样例 #1
样例输入 #1
5 7
1 1 0
1 2 0
2 2 1
3 3 1
3 4 0
4 4 1
5 5 0
样例输出 #1
8
样例 #2
样例输入 #2
5 5
1 1 0
1 2 0
2 2 1
3 3 1
5 5 0
样例输出 #2
-1
提示
样例 1 说明
棋盘的颜色如下表格所示，其中空白的部分表示无色。
| 红 \color{red}\text{红} 红 | 红 \color{red}\text{红} 红 | |||
|---|---|---|---|---|
| 黄 \color{yellow}\text{黄} 黄 | ||||
| 黄 \color{yellow}\text{黄} 黄 | 红 \color{red}\text{红} 红 | |||
| 黄 \color{yellow}\text{黄} 黄 | ||||
| 红 \color{red}\text{红} 红 |
从 ( 1 , 1 ) (1,1) (1,1) 开始，走到 ( 1 , 2 ) (1,2) (1,2) 不花费金币。
从 ( 1 , 2 ) (1,2) (1,2) 向下走到 ( 2 , 2 ) (2,2) (2,2) 花费 1 1 1 枚金币。
从 ( 2 , 2 ) (2,2) (2,2) 施展魔法，将 ( 2 , 3 ) (2,3) (2,3) 变为黄色，花费 2 2 2 枚金币。
从 ( 2 , 2 ) (2,2) (2,2) 走到 ( 2 , 3 ) (2,3) (2,3) 不花费金币。
从 ( 2 , 3 ) (2,3) (2,3) 走到 ( 3 , 3 ) (3,3) (3,3) 不花费金币。
从 ( 3 , 3 ) (3,3) (3,3) 走到 ( 3 , 4 ) (3,4) (3,4) 花费 1 1 1 枚金币。
从 ( 3 , 4 ) (3,4) (3,4) 走到 ( 4 , 4 ) (4,4) (4,4) 花费 1 1 1 枚金币。
从 ( 4 , 4 ) (4,4) (4,4) 施展魔法，将 ( 4 , 5 ) (4,5) (4,5) 变为黄色，花费 $ 2$ 枚金币。
从 ( 4 , 4 ) (4,4) (4,4) 走到 ( 4 , 5 ) (4,5) (4,5) 不花费金币。
从 ( 4 , 5 ) (4,5) (4,5) 走到 ( 5 , 5 ) (5,5) (5,5) 花费 1 1 1 枚金币。
共花费 $8 $ 枚金币。
样例 2 说明
棋盘的颜色如下表格所示，其中空白的部分表示无色。
| 红 \color{red}\text{红} 红 | 红 \color{red}\text{红} 红 | |||
|---|---|---|---|---|
| 黄 \color{yellow}\text{黄} 黄 | ||||
| 黄 \color{yellow}\text{黄} 黄 | ||||
| \color{white}\text{ } | ||||
| 红 \color{red}\text{红} 红 |
从 ( 1 , 1 ) ( 1, 1) (1,1) 走到 ( 1 , 2 ) ( 1, 2) (1,2)，不花费金币。
从 ( 1 , 2 ) ( 1, 2) (1,2) 走到 ( 2 , 2 ) ( 2, 2) (2,2)，花费 $ 1 $ 金币。
施展魔法将 ( 2 , 3 ) ( 2, 3) (2,3) 变为黄色，并从 ( 2 , 2 ) ( 2, 2) (2,2) 走到 ( 2 , 3 ) ( 2, 3) (2,3) 花费 $ 2$ 金币。
从 ( 2 , 3 ) ( 2, 3) (2,3) 走到 ( 3 , 3 ) ( 3, 3) (3,3) 不花费金币。
从 ( 3 , 3 ) ( 3, 3) (3,3) 只能施展魔法到达 ( 3 , 2 ) , ( 2 , 3 ) , ( 3 , 4 ) , ( 4 , 3 ) ( 3, 2),( 2, 3),( 3, 4),( 4, 3) (3,2),(2,3),(3,4),(4,3)。
而从以上四点均无法到达 ( 5 , 5 ) ( 5, 5) (5,5)，故无法到达终点，输出 − 1 -1 −1。
数据规模与约定
对于 30 % 30\% 30% 的数据， 1 ≤ m ≤ 5 , 1 ≤ n ≤ 10 1 ≤ m ≤ 5, 1 ≤ n ≤ 10 1≤m≤5,1≤n≤10
对于 60 % 60\% 60% 的数据， 1 ≤ m ≤ 20 , 1 ≤ n ≤ 200 1 ≤ m ≤ 20, 1 ≤ n ≤ 200 1≤m≤20,1≤n≤200
对于 100 % 100\% 100% 的数据， 1 ≤ m ≤ 100 , 1 ≤ n ≤ 1 , 000 1 ≤ m ≤ 100, 1 ≤ n ≤ 1,000 1≤m≤100,1≤n≤1,000
该题和之前的迷宫问题相比就多了一个操作，就是可以使用魔法改变格子的颜色。
对于有色的格子，正常的考虑前后两个格子的颜色计算花费即可。
对于无色的格子，先要考虑把无色格子的颜色变为哪种颜色最优？或者两种颜色都需要考虑？分情况考虑后发现把无色格子的颜色变为上一个格子的颜色花费不会高与变为不同的颜色，所以每次改变无色格子颜色时就要变为与上一个格子相同颜色。
在执行搜索操作时，先要考虑情况，要传递哪些参数，这些参数会发生怎样的变化。
参数1：坐标，和之前搜索的变化相同。
参数2：花费，相同为0，不同为1，改变为2
参数3：因为魔法不能连续使用，所以还需要记录上一次是否使用过魔法。如果使用过，并且当前格子是无色，那么就不能继续走下去了。
参数4：因为需要比较前后两个格子的颜色，并且颜色还可以改变，所以还需要记录上一个格子的颜色,如果直接和a[x][y]比较，会出现问题。因为颜色时临时改变，离开后颜色会还原，所以改变无色格子时不能直接修改原数组，否则下次访问时就会出现问题。
#include <bits/stdc++.h>
using namespace std;
const int N=1100;
const int dx[4]= {1,-1,0,0};
const int dy[4]= {0,0,1,-1};
int g[N][N],n,m,dis[N][N],vis[N][N],ans=1e9;
int check(int x,int y){
if (x<1 || x>n || y<1 || y>n || vis[x][y])
return true;
return false;
}
void dfs(int x,int y,int nowc,int r){
if(x==n && y==n && r<ans){
ans=r;
return;
}
if(r>=dis[x][y])
return;
dis[x][y]=r;
for(int i=0; i<4; i++){
int xx=x+dx[i],yy=y+dy[i],cl=g[xx][yy];
if (check(xx,yy))
continue;
vis[xx][yy]=true;
if(nowc>=3 && cl!=0){
if((nowc+cl)%2==0)
dfs(xx,yy,cl,r);
else
dfs(xx,yy,cl,r+1);
}
else if(nowc==1 || nowc==2){
if(cl==1 || cl==2){
if(nowc!=cl)
dfs(xx,yy,cl,r+1);
else
dfs(xx,yy,cl,r);
}
else
dfs(xx,yy,nowc+2,r+2);
}
vis[xx][yy]=false;
}
}
int main(){
cin>>n>>m;
memset(dis,0x3f,sizeof(dis));
for(int i=1; i<=m; i++){
int x,y,c;
cin>>x>>y>>c;
g[x][y]=c+1;
}
vis[1][1]=true;
dfs(1,1,g[1][1],0);
if (ans==1e9)
cout<<-1;
else
cout<<ans;
return 0;
}
回家
题目描述
小 H 在一个划分成了 n × m n \times m n×m 个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格（当然小 H 不可以静止不动）， 但不能离开封锁线，否则就被打死了。 刚开始时他有满血 6 6 6 点，每移动一格他要消耗 1 1 1 点血量。一旦小 H 的血量降到 0 0 0， 他将死去。 他可以沿路通过拾取鼠标（什么鬼。。。）来补满血量。只要他走到有鼠标的格子，他不需要任何时间即可拾取。格子上的鼠标可以瞬间补满，所以每次经过这个格子都有鼠标。就算到了某个有鼠标的格子才死去， 他也不能通过拾取鼠标补满 HP。 即使在家门口死去， 他也不能算完成任务回到家中。
地图上有五种格子：
0：障碍物。
1：空地， 小 H 可以自由行走。
2：小 H 出发点， 也是一片空地。
3：小 H 的家。
4：有鼠标在上面的空地。
小 H 能否安全回家？如果能， 最短需要多长时间呢？
输入格式
第一行两个整数 n , m n,m n,m， 表示地图的大小为 n × m n \times m n×m。
下面 n n n 行， 每行 m m m 个数字来描述地图。
输出格式
一行， 若小 H 不能回家， 输出 -1，否则输出他回家所需最短时间。
样例 #1
样例输入 #1
3 3
2 1 1
1 1 0
1 1 3
样例输出 #1
4
提示
对于所有数据， 1 ≤ n , m ≤ 9 1 \le n,m \le 9 1≤n,m≤9。
2021.9.2 增添一组 hack 数据 by @囧仙
该题要求最短路径，看上去是一道深搜求最短路的题，但是实际上直接求解最短路答案是错误的。
因为该题的前提是在活着回家的前提下路径最短，可能会出现一种情况，比如小H可能需要先绕道去吃一个血包补充血量后再返回来继续往前走，否则他就无法安全到达家，比如。
他必须先到红色位置吃了血包再返回来去终点，否则就到不了家，这里的最短路有重复路径。
在搜索问题中，我们采用的是做标记的办法来防止死循环。但是该题，可能存在同一个点被多次走的情况，如果按照之前的方式标记，那么可能找不到正确答案，如果不标记，那么可能会死循环。
所以该题仍然要标记，但是标记的含义和之前有一点区别。第一种思路是，虽然一个点可以走多次，但是吃了血包之后血量瞬间回满，所以在最短路径上的点最多走两次，所以book数组不仅仅表示标记，还表示走过的次数，当book[x][y]的值为2时才不可以走。
第二种思路也是在原有的标记上进行修改，还是思考当经过一个点两次时，什么情况下可能是最短路，什么情况下不可能是最短路。
我们绕路的原因是吃血包，也就是当下一次经过这个格子时血量会增加，如果重复经过一个格子时血量没有增加，那么肯定就不会是最短路径。所以标记的时候book不仅表示走过了改点，还表示经过改点的血量，所以book的值为到达当前点的血量值。
所以在搜索中，标记的含义是很灵活的，不仅用来表示是否到达，还可以记录一些其他信息。
该题还有很多细节需要注意：
1、因为到达该点，无论该点是什么，只要没血了都会死亡，所以到达一个点的时候最先判断血量。
2、在考虑1的情况下，仍然会出现到达血包位置血量为0的情况，所以走可以的条件最好改为当前血量>=1
3、由于该题可以走重复路径，所以之前常用的第二种最优性剪枝就无法使用，只能使用第一种剪枝办法，直接判断当前路径和之前最短路径的大小关系。
#include<bits/stdc++.h>
using namespace std;
int mp[20][20],n,m,a,b,c,d,minn=INT_MAX;
int dis[20][20][8],used[20][20];
int dr[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
void dfs(int x,int y,int blood,int cnt){
if (x>n||x<1||y>m||y<1||mp[x][y]==0||cnt>n*m||cnt>minn||blood==0)return;
if (cnt>dis[x][y][blood])return;
dis[x][y][blood]=cnt;
//cout<<2<<endl;
if (mp[x][y]==4)blood=6;
if (x==c&&y==d&&blood>0){
// cout<<4<<endl;
minn=min(cnt,minn);
return;
}
for (int i=0;i<4;i++){
int rx=x+dr[i][0],ry=y+dr[i][1];
dfs(rx,ry,blood-1,cnt+1);
}
return;
}
int main(){
for (int i=0;i<20;i++){
for (int j=0;j<20;j++){
for (int k=0;k<8;k++){
dis[i][j][k]=INT_MAX;
}
}
}
cin>>n>>m;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
cin>>mp[i][j];
if (mp[i][j]==2)a=i,b=j;
if (mp[i][j]==3)c=i,d=j;
}
}
// cout<<a<<" "<<b;
dfs(a,b,6,0);
if (minn==INT_MAX)cout<<-1;
else cout<<minn;
return 0;
}
天总共打了15000多字！都这样了你还不把你手中的点赞和收藏送出来的话，太过分了！