2027.7.23深搜算法复习总结
P1683 入门
题目描述
不是任何人都可以进入桃花岛的，黄药师最讨厌像郭靖一样呆头呆脑的人。所以，他在桃花岛的唯一入口处修了一条小路，这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩，我们认为是安全的，而有的瓷砖一踩上去就会有喷出要命的毒气，那你就死翘翘了，我们认为是不安全的。你只能从一块安全的瓷砖上走到与他相邻的四块瓷砖中的任何一个上，但它也必须是安全的才行。
由于你是黄蓉的朋友，她事先告诉你哪些砖是安全的、哪些砖是不安全的，并且她会指引你飞到第一块砖上（第一块砖可能在任意安全位置），现在她告诉你进入桃花岛的秘密就是：如果你能走过最多的瓷砖并且没有死，那么桃花岛的大门就会自动打开了，你就可以从当前位置直接飞进大门了。
注意：瓷砖可以重复走过，但不能重复计数。
输入格式
第一行两个正整数 W 和 H，分别表示小路的宽度和长度。
以下 H 行为一个 H×W 的字符矩阵。每一个字符代表一块瓷砖。其中，. 代表安全的砖，# 代表不安全的砖，@ 代表第一块砖。
输出格式
输出一行，只包括一个数，即你从第一块砖开始所能安全走过的最多的砖块个数（包括第一块砖）。
输入输出样例
输入 #1
11 9 .#......... .#.#######. .#.#.....#. .#.#.###.#. .#.#..@#.#. .#.#####.#. .#.......#. .#########. ...........
输出 #1
59
说明/提示
数据规模与约定
对于全部的测试点，保证 1≤W,H≤20。
解法
使用深搜，枚举每一个点的走法，这里题目说可以重复走过，但不能重复计数，其实就跟广搜一个道理，所以我们完全可以使用广搜的方法写，但因为这里不能重复走，所以不用回溯
题解
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void dfs(int a,int b)
{sum++;g[a][b]='#';for(int i=0;i<4;i++){int x=a+dx[i];int y=b+dy[i];if(x>=1&&x<=m&&y>=1&&y<=n&&g[x][y]!='#') {g[x][y]='#';dfs(x,y);}}
}
for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)if(g[i][j]=='@') dfs(i,j);错误
题目中说输入n,m，结果要m行n列的矩阵，这里写反了
P2802 回家
题目描述
小 H 在一个划分成了 n×m 个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格（当然小 H 不可以静止不动）， 但不能离开封锁线，否则就被打死了。 刚开始时他有满血 6 点，每移动一格他要消耗 1 点血量。一旦小 H 的血量降到 0， 他将死去。 他可以沿路通过拾取鼠标（什么鬼。。。）来补满血量。只要他走到有鼠标的格子，他不需要任何时间即可拾取。格子上的鼠标可以瞬间补满，所以每次经过这个格子都有鼠标。就算到了某个有鼠标的格子才死去， 他也不能通过拾取鼠标补满 HP。 即使在家门口死去， 他也不能算完成任务回到家中。
地图上有五种格子：
0：障碍物。
1：空地， 小 H 可以自由行走。
2：小 H 出发点， 也是一片空地。
3：小 H 的家。
4：有鼠标在上面的空地。
小 H 能否安全回家？如果能， 最短需要多长时间呢？
输入格式
第一行两个整数 n,m， 表示地图的大小为 n×m。
下面 n 行， 每行 m 个数字来描述地图。
输出格式
一行， 若小 H 不能回家， 输出 -1，否则输出他回家所需最短时间。
输入输出样例
输入 #1
3 3 2 1 1 1 1 0 1 1 3
输出 #1
4
说明/提示
对于所有数据，1≤n,m≤9。
2021.9.2 增添一组 hack 数据 by @囧仙
解法
跟上面一道题差不多，但要判断脚底下的数有什么作用，所以dfs里面还要传进去两个参数，一个存步数，一个存血量，每次调用，步数+1，血量-1
题解
void dfs(int a,int b,int l,int t)
{if(t>res) return;if(l==0) return;if(g[a][b]==4) l=6;if(g[a][b]==3){res=min(res,t);return;}g[a][b]=0;for(int i=0;i<4;i++){int x=a+dx[i];int y=b+dy[i];if(x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]!=0){int d=g[x][y];dfs(x,y,l-1,t+1);g[x][y]=d;}}
}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(g[i][j]==2){g[i][j]=0;dfs(i,j,6,0);}但是这么做会有一个点TLE，另一个WA，那么我们考虑怎么优化
优化
在dfs中，可能会调用多次一个点，所以我们可以定义一个三维数组，来存这个点的答案，如果这个点访问过，那么直接return
优化后的代码
void dfs(int a,int b,int l,int t)
{if(t>=dp[a][b][l]) return;dp[a][b][l]=t;if(l==0) return;if(g[a][b]==4) l=6;if(g[a][b]==3){res=min(res,t);return;}for(int i=0;i<4;i++){int x=a+dx[i];int y=b+dy[i];if(x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]!=0){dfs(x,y,l-1,t+1);}}
}其余一样，这里不贴了
P2080 增进感情
题目背景
小明和小红的感情，是慢慢发展起来的。
题目描述
他们对对方分别有一个好感值。定义两人的亲密程度为两人的好感值之和。
如果他们的亲密程度达到 v，则他们将走到一起。他们以后的生活将取决于两人的好感值之差的绝对值，这个值越小，他们的生活将越幸福。
现在，他们对对方的好感值都为 0，小明有 n 件事可以干，每件事可以增加他对小红的好感 ai 点，并且增加小红对他的好感 bi 点。（可能为负数）
小明可以任选一些事做，请你帮小明求出怎样才能让他们的生活更加幸福（求出两人在一起的前提下，好感值之差的最小绝对值即可）。
输入格式
第一行，两个正整数 n,v。
之后 n 行，每行两个空格隔开的整数 ai,bi。
输出格式
一行，一个非负整数，表示两人在一起的前提下，好感值之差的最小绝对值。如果无论如何两人也无法在一起，输出 -1。
输入输出样例
输入 #1
4 15 5 6 -1 8 7 2 1 0
输出 #1
3
说明/提示
数据范围与约定
- 对于 20% 数据，保证 n≤10。
- 对于 100% 数据，保证 1≤n≤30，1≤∣ai∣,∣bi∣≤100。
解法
这道题直接暴力搜索，将这件事分为做与不做两个状态分别dfs，复杂度虽然有1e9但不会超时
题解
void dfs(int u,int s1,int s2)
{if(u>n){if(s1+s2>=v) res=min(res,abs(s1-s2));return;}dfs(u+1,s1,s2);dfs(u+1,s1+a[u],s2+b[u]);
}dfs(1,0,0);P5635 【CSGRound1】天下第一
题目背景
天下第一的 cbw 以主席的身份在 8102 年统治全宇宙后，开始了自己休闲的生活，并邀请自己的好友每天都来和他做游戏。由于 cbw 想要显出自己平易近人，所以 zhouwc 虽然是一个蒟蒻，也有能和 cbw 玩游戏的机会。
题目描述
游戏是这样的：
给定两个数 x，y，与一个模数 p。
cbw 拥有数 x，zhouwc 拥有数 y。
第一个回合：x←(x+y) mod p。
第二个回合：y←(x+y) mod p。
第三个回合：x←(x+y) mod p。
第四个回合：y←(x+y) mod p。
以此类推....
如果 x 先到 0，则 cbw 胜利。如果 y 先到 0，则 zhouwc 胜利。如果 x,y 都不能到 0，则为平局。
cbw 为了捍卫自己主席的尊严，想要提前知道游戏的结果，并且可以趁机动点手脚，所以他希望你来告诉他结果。
输入格式
有多组数据。
第一行：T 和 p 表示一共有 T 组数据且模数都为 p。
以下 T 行，每行两个数 x,y。
输出格式
共 T 行
1 表示 cbw 获胜，2 表示 zhouwc 获胜，error 表示平局。
输入输出样例
输入 #1
1 10 1 3
输出 #1
error
输入 #2
1 10 4 5
输出 #2
1
说明/提示
1≤T≤200。
1≤x,y,p≤10000。
解法
这道题也可以暴力，定义一个vis数组来保存答案，如果x和y与以前的x，y重复就可以直接return vis[x][y]，然后这里可以定义一个变量来存储是x的回合还是y的回合，注意这里可能调用的数一样，但标记的数不一样，所以要特判
题解
int dfs(int op,int x,int y)
{if(op==0){if(vis[x][y]!=-1) return vis[x][y];vis[x][y]=0;if(x==0) return vis[x][y]=1;if(y==0) return vis[x][y]=2;int a=x,b=y;if(op==0) x=(x+y)%p;else y=(x+y)%p;return vis[a][b]=dfs(!op,x,y); }else{if(x==0) return vis[x][y]=1;if(y==0) return vis[x][y]=2;int a=x,b=y;if(op==0) x=(x+y)%p;else y=(x+y)%p;return dfs(!op,x,y); }}memset(vis,-1,sizeof vis);
while(t--)
{int x,y;cin>>x>>y;if(dfs(0,x,y)) cout<<dfs(0,x,y)<<"\n";else cout<<"error\n";
}错误
就是刚刚解法说的xy与op的关系
P2919 [USACO08NOV] Guarding the Farm S
题目描述
农场有许多小山丘，约翰农夫希望在这些小山丘上放置守卫，以确保他珍贵的奶牛的安全。
他想知道如果他希望在每个小山丘的顶部放置一个守卫，他需要多少守卫。他有一张地图，这张地图是一个整数矩阵；矩阵有 N 行（1<N≤700）和 M 列（1<M≤700）。矩阵中的每个元素表示一个高度 Hij（0≤Hij≤10,000）。请帮助他确定地图上有多少个山顶。
一个山顶是由一个或多个相邻且具有相同值的矩阵元素组成，这些元素被地图的边缘或具有较低（较小）高度的元素完全包围。如果两个不同的元素的 X 坐标差的绝对值不大于 1，且 Y 坐标差的绝对值也不大于 1，则它们是相邻的。
输入格式
* 第 1 行：两个用空格分隔的整数：N 和 M
* 第 2 行到第 N+1 行：第 i+1 行描述矩阵的第 i 行，包含 M 个用空格分隔的整数：Hij
输出格式
* 第 1 行：一个整数，表示山顶的数量
题意翻译
显示翻译
输入输出样例
输入 #1
8 7 4 3 2 2 1 0 1 3 3 3 2 1 0 1 2 2 2 2 1 0 0 2 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 2 2 1 1 0 0 1 1 1 2 1 0
输出 #1
3
说明/提示
有三个山峰：左上角高度为 4 的一个，底部高度为 2 的一个点，以及右上角高度为 1 的一个点。 （由 ChatGPT 4o 翻译）
解法
可以使用结构体排序，将每座山峰的高度排序，然后再通过类似求联通块的方式来求答案
题解
struct node
{int h,a,b;
}p[1000025];
bool cmp(node x,node y)
{return x.h>y.h;
}
void dfs(int a,int b)
{for(int i=0;i<8;i++){int x=a+dx[i];int y=b+dy[i];if(x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]<=g[a][b]&&vis[x][y]==0){vis[x][y]=1;dfs(x,y);}}
}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>g[i][j];p[++idx]={g[i][j],i,j};}
sort(p+1,p+1+idx,cmp);
for(int i=1;i<=idx;i++)
{if(vis[p[i].a][p[i].b]==0){vis[p[i].a][p[i].b]=1;dfs(p[i].a,p[i].b);cnt++;}
}