!搜索（DFS&&BFS）！（校内题解，题目来自洛谷和百练poj）
题目：
1.迷宫——洛谷搜索题单1605
2.马的遍历——洛谷搜索题单1443
3.填涂颜色——洛谷搜索题单1162
4.棋盘问题——百练1321
5.马走日——百练4123
6.红与黑——百练2816
7.奇怪的电梯——洛谷搜索题单1135
8.迷宫问题——百练4127
9.Meteor Shower S——洛谷搜索题单2895
10. Corn Maze S——洛谷搜索题单1825
11.八皇后 Checker Challenge——洛谷搜索题单1219
12.单词接龙——洛谷搜索题单1019
本文主要目的是自我记录🤪🌹
搜索
搜索主要划分为 深度优先搜索（dfs）&& 广度优先搜索（bfs），可分，那两者肯定有区别，先说说深搜。
深搜：
&1（搜索方向）：主打一个一条路走到黑，不撞南墙不回头，到尾后回退到最近一个“分岔口”
&2（应用方向）：暴力搜索（ 没有单调性的最大值，最小值），能实现的方案数等等等等
&3（模板）：
void dfs(达到目的前的某一步)
{
if(达到目的) return ;
(剪枝)
for(枚举所有可能解)
{
if(不满足) continue；
mark;
dfs(达到目的前的某一步+1);
取消mark;
}
}
广搜：
&1（搜索方向）：多路同时进行——看图说话（狗头）
&2（应用方向）：因为多路同时进行的原因，可以用于搜索最短路，也可以用于遍历等等等等
&3（模板）：
#include//头文件
int main()
{
queue q;
q.push(首元素);//向队列增加元素
while(q.size())
{
p=q.front();//获取队列第一个
q.pop();//删除队列第一个
for(枚举所有可能解)
{
if(不满足) continue;
mark;
q.push(当前元素);
}
}
}
前置
如果是需要上下左右走的，而小伙伴们不知道怎么写，可以参考如下代码
（ab约束依照题目）
int xi[4]={-1,1,0,0},yj[4]={0,0,-1,1};
……
for(i=0;i<4;i++)
{
a=x+xi[i];
b=y+yj[i];
if(a<1||bn||b>m||map[a][b]==1) continue;
……
}
1.迷宫——洛谷搜索题单1605
1.迷宫——洛谷搜索题单1605
思路：dfs模板题吧？暴力搜索——走过就打1，走完就回退，回退取消1
代码：
#include
using namespace std;
int n,m,ei,ej,ans,map[10][10],xi[4]={-1,1,0,0},yj[4]={0,0,-1,1};
void dfs(int x,int y)
{
int i,a,b;
if(x==ei&&y==ej)
{
ans++;
return ;
}
for(i=0;i<4;i++)
{
a=x+xi[i];
b=y+yj[i];
if(a<1||bn||b>m||map[a][b]==1) continue;
map[a][b]=1;
dfs(a,b);
map[a][b]=0;
}
}
int main()//1605——迷宫
{
int i,j,k,t,bi,bj;
cin>>n>>m>>t;
cin>>bi>>bj>>ei>>ej;
map[bi][bj]=1;
for(k=0;k>i>>j;
map[i][j]=1;
}
dfs(bi,bj);
cout<
2.马的遍历——洛谷搜索题单1443
2.马的遍历——洛谷搜索题单1443
思路：能跳到的点为上一个点所跳步数+1，类似递推桶，基于广搜原理的题，多路同时进行，跳跳跳（狗头）
&1，初始化地图
&2，多路同时进行，能跳到的点为上一个点所跳步数+1，“打上标记”
memset函数：将 某一块内存 中的全部元素 设置成 指定值
memset（变量名，指定值，大小（可用sizeof函数））
代码：
#include
#include
#include
using namespace std;
int c[405][405],xi[8]={-1,-2,-2,-1,1,2,2,1},yj[8]={-2,-1,1,2,2,1,-1,-2};
struct point{
int a,b;
}p;
int main()//1443——马的遍历
{
int n,m,x,y,px,py,i,j;
queue q;
memset(c,-1,sizeof(c));//头文件csrting
cin>>n>>m>>x>>y;
c[x][y]=0;
q.push(point{x,y});
while(q.size())
{
p=q.front();
q.pop();
for(i=0;i<8;i++)
{
px=xi[i]+p.a;
py=yj[i]+p.b;
if(pxn||pym||c[px][py]!=-1) continue;
c[px][py]=c[p.a][p.b]+1;
q.push(point{px,py});
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++) cout<<c[i][j]<<" ";//题目需求
cout<<endl;
}
return 0;
}
3.填涂颜色——洛谷搜索题单1162
3.填涂颜色——洛谷搜索题单1162
思路：遍历地图！广搜！
&1，因为1内的0不能被搜到，所以可用一个假地图来 “存入” 地图1外全部0信息
&2，为了防止1在边界导致广搜不到0，在地图外再加一圈0
&3，输出根据真假地图来输出
代码：
#include
#include
using namespace std;
int map[35][35],fmap[35][35],xi[4]={-1,1,0,0},yj[4]={0,0,-1,1};
struct point{
int a,b;
}p;
int main()//1162
{
int i,j,n,x,y;
queue q;
cin>>n;
for(i=1;i<n+1;i++)
{
for(j=1;j>map[i][j];
}
fmap[0][0]=1;
q.push(point{0,0});
while(q.size())
{
p=q.front();
q.pop();
for(i=0;i<4;i++)
{
x=p.a+xi[i];
y=p.b+yj[i];
if(xn+1||yn+1||fmap[x][y]==1) continue;
if(map[x][y]==0&&fmap[x][y]==0)
{
fmap[x][y]=1;
q.push(point{x,y});
}
}
}
for(i=1;i<n+1;i++)
{
for(j=1;j<n+1;j++)
{
if(map[i][j]==0&&fmap[i][j]==1) cout<<"0 ";
else if(map[i][j]==1&&fmap[i][j]==0) cout<<"1 ";
else cout<<"2 ";
}
cout<<endl;
}
return 0;
}
4.棋盘问题——百练1321
4.棋盘问题——百练1321
思路：其实这道题望眼欲穿，这不就是排列组合吗？直接上 C（可塞棋子位数）^ (棋子数），不幸的是wa了，这题需要高精度……
言归正传……方案数——深搜，但是这是一道好题，与深搜水题不同——棋子不一定每行都有，这该怎么办？莫急，转念一想，就是相当于多了暴搜某些行不枚举罢了
&1，使用b[j]表示这一列都被标记过，灵活变通（狗头）
&2，暴力枚举每一行，能塞就塞，打标记，棋子摆放完，去除标记
&3，某些行不枚举……
那怎么实现？其实很简单
void dfs(int x,int last)
{
int j;
if(last==0)
{
ans++;
return ;
}
if(x>n) return ;//越界
for(j=1;j<=n;j++)
{
if(b[j]||a[x][j]) continue;
b[j]=1;
dfs(x+1,last-1);
b[j]=0;
}
}
这是我们每一行都搜的情况，我们只需要加入dfs（x+1，last）；即可。这句代码表示这行我不搜
代码：
#include
using namespace std;
int n,k,ans,a[10][10],b[10];
void dfs(int x,int last)
{
int j;
if(last==0)
{
ans++;
return ;
}
if(x>n) return ;//越界
for(j=1;j>n>>k;
if(n==-1&&k==-1) break;
for(i=1;i<=n;i++)
{
for(j=1;j>ch;
if(ch=='#') a[i][j]=0;
else a[i][j]=1;
}
}
for(i=1;i<=n;i++) b[i]=0;
ans=0;
dfs(1,k);
cout<
5.马走日——百练4123
5.马走日——百练4123
思路：又是一道深搜模板题！方案数？深搜！只不过判断条件变成了 能跳的次数是否等于n*m
可能有的小伙伴会问，如果cnt小于n*m那是不是出不来函数了？其实不然，因为这种情况就是说明8个方向都continue了，进不去下一个dfs了
值得一提的是，方向坐标不能设置成全局变量（捂脸）
代码：
#include
#include
using namespace std;
int n,m,sum,map[15][15],xi[8]={-1,-2,-2,-1,1,2,2,1},yj[8]={-2,-1,1,2,2,1,-1,-2};
void dfs(int x,int y,int cnt)
{
int i,a,b;//a,b不能是全局变量
if(cnt==n*m)
{
sum++;
return ;
}
for(i=0;i<8;i++)
{
a=x+xi[i];
b=y+yj[i];
if(a=n||b=m||map[a][b]==1) continue;
map[a][b]=1;
dfs(a,b,cnt+1);
map[a][b]=0;
}
}
int main()
{
int t,x0,y0,i,j;
cin>>t;
while(t--)
{
memset(map,0,sizeof(map));
cin>>n>>m>>x0>>y0;
map[x0][y0]=1;
sum=0;
dfs(x0,y0,1);
cout<<sum<<endl;
}
return 0;
}
6.红与黑——百练2816
6.红与黑——百练2816
思路：深搜广搜都行，每个可以走的块都加1即可。
用dfs写不需要取消标记，因为我们现在是遍历整张地图！
我提供的代码可能有的小伙伴会问ans怎么会加啊？dfs里不就只有一个ans+=嵌套的dfs吗？奥秘蕴藏在return中，每一个能走的dfs本身的ans就是1。最后一个能遍历到的点的ans是1，它就会回退，那么它的回退dfs就会加上它的ans（也就是1），然后退退退，退回最终所有能遍历点的个数
代码：
#include
#include
using namespace std;
int n,m,map[25][25],xi[4]={-1,1,0,0},yj[4]={0,0,-1,1};
int dfs(int x,int y)
{
int a,b,i,ans=1;
for(i=0;in||y>m||x<1||y>m>>n;
if(m==0&&n==0) break;
memset(map,1,sizeof(map));
for(i=1;i<=n;i++)
{
for(j=1;j>ch;
if(ch=='.') map[i][j]=0;
else if(ch=='@')
{
x0=i;
y0=j;
}
}
}
cout<<dfs(x0,y0)<<endl;
}
return 0;
}
7.奇怪的电梯——洛谷搜索题单1135
7.奇怪的电梯——洛谷搜索题单1135
思路：本题答案不具有单调性，贪心不知道能不能写。暴搜吧，放弃了，交给计算机……
但是！本题需要剪枝，否则就要tle了！
那该怎么剪？经过 反证法 我们发现 能通往答案的每一层楼，它的步数都是最小的！所以剪这部分
代码：
#include
using namespace std;
int s[205],fs[205],n,a,b,ans=1e9;
void dfs(int change,int solid,int fans)
{
if(changen||fans>=ans||fans>=fs[change]) return ;
if(change==solid)
{
ans=min(fans,ans);
return ;
}
fs[change]=min(fans,fs[change]);
dfs(change+s[change],solid,fans+1);
dfs(change-s[change],solid,fans+1);
}
int main()//1135
{
int i;
cin>>n>>a>>b;
for(i=1;i>s[i];
fs[i]=1e9;
}
dfs(a,b,0);
if(ans!=1e9) cout<
8.迷宫问题——百练4127
思路：这题是道Boss题。难就难在怎么输出坐标？
以下是广搜路线
我们发现这个坐标也就是树，它可以子推亲，但是不能亲推子
从4，4->0,0
结构体具有这样的性质，所以我们用 子“套”亲
struct point{
int 亲.x,亲.y;
}mark[子.x][子.y];
子坐标内存的是子的亲坐标，所以我们可以用递归一层一层的 套 出来，但是0，0没有亲！所以单独输出
代码：
#include
#include
using namespace std;
int map[10][10],xi[4]={-1,1,0,0},yj[4]={0,0,-1,1};
struct point{
int x,y;
}p,mark[10][10];
void put(int xa,int yb)
{
if(xa==0&&yb==0) return ;
p.x=mark[xa][yb].x;
p.y=mark[xa][yb].y;
put(p.x,p.y);
cout<<"("<<xa<<", "<<yb<<")"<<endl;
}
int main()
{
int i,j,a,b;
queue q;
for(i=0;i<5;i++)
{
for(j=0;j>map[i][j];
}
q.push(point{0,0});
map[0][0]=1;
while(q.size())
{
p=q.front();
q.pop();
for(i=0;i<4;i++)
{
a=p.x+xi[i];
b=p.y+yj[i];
if(a=5||b=5||map[a][b]==1) continue;
map[a][b]=1;
mark[a][b].x=p.x;
mark[a][b].y=p.y;
q.push(point{a,b});
}
}
cout<<"(0, 0)"<<endl;
put(4,4);
return 0;
}
9.Meteor Shower S——洛谷搜索题单2895
9.Meteor Shower S——洛谷搜索题单2895
思路： 广搜。对所有点的时间设置-1，然后存储这个点被砸的时间，人走当前能走的点（即人走到这个点的时间小于被砸的时间或者-1）/*现在的-1表示这个点没有被砸*/，走到-1即可。
注意：&1，赋值不能越界（放这个图就懂了），因为作者i,j<306RE了
&2，memset会将结构体5变量全设置成-1（上文里的全部）
&3，如果数据后有流星时间小于数据前被砸的点的时间，更新
&4，先前我的判定是写成下面的代码，但是wa了
因为 s[dx][dy].t==-1时 也是小于p.step+1 会跳过，就没有正确答案了。想这么写的小伙伴加个&&就好了
if(dx<0||dy<0||s[dx][dy].mark==1||s[dx][dy].t<=p.step+1) continue;
s[dx][dy].step=p.step+1;
s[dx][dy].mark=1;
if(s[dx][dy].t==-1)
{
cout<<s[dx][dy].step;
return 0;
}
q.push(s[dx][dy]);
代码：
#include
#include
#include
using namespace std;
int xi[5]={-1,1,0,0,0},yj[5]={0,0,-1,1,0};
struct map{
int x,y,t,step,mark;
}p,s[305][305];
int main()//2895
{
int m,i,j,k,dt,a,b,dx,dy;
memset(s,-1,sizeof(s));//将结构体5个变量全设成-1
queue
10. Corn Maze S——洛谷搜索题单1825
10. Corn Maze S——洛谷搜索题单1825
思路：广搜！只不过多了个传送门罢了，小场面来的。
&1，用结构体存储两个传送门，遇到其中一个，直接调用另一个
&2，使用传送门step不加，传送门不打标记，原因如下
#########=
####.@.Q..
.....####.
.....####.
###..####.
###Q.####.
####......
这个最短路用了两次传送门，先往右遇到传送门，从传送门出来，再从传送门进去
代码：
#include
#include
using namespace std;
char map[305][305],ch;
int xi[4]={-1,1,0,0},yj[4]={0,0,-1,1};
struct P{
int x1,y1,x2,y2;
}s[100];
struct point{
int x,y,step;
}p;
int main()//1825
{
int n,m,i,j,a,b;
queue q;
cin>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j>map[i][j];
ch=map[i][j];
if(ch>='A'&&ch<='Z')
{
if(s[ch].x1==0)
{
s[ch].x1=i;
s[ch].y1=j;
}
else
{
s[ch].x2=i;
s[ch].y2=j;
}
}
if(ch=='@')
{
q.push(point{i,j,0});
map[i][j]='#';
}
}
}
while(q.size())
{
p=q.front();
q.pop();
for(i=0;i<4;i++)
{
a=p.x+xi[i];
b=p.y+yj[i];
ch=map[a][b];
if(an||bm||map[a][b]=='#') continue;
if(ch=='=')
{
cout<<p.step+1;
return 0;
}
if(ch=='.')
{
q.push(point{a,b,p.step+1});
map[a][b]='#';
}
if(s[ch].x1==a&&s[ch].y1==b) q.push(point{s[ch].x2,s[ch].y2,p.step+1});
else q.push(point{s[ch].x1,s[ch].y1,p.step+1});
}
}
return 0;
}
11.八皇后 Checker Challenge——洛谷搜索题单1219
11.八皇后 Checker Challenge——洛谷搜索题单1219
思路：这题与棋盘问题不同，多了对角线限定，但少了棋子限定，方法还是dfs。
那现在就来找找主副对角线上有什么规律（不可能去遍历每一个点来判定的）
z表示一个未知数
我们发现 任一主对角线的 i+j 永远等于一个特定值 ； 而任一副对角线 j-i 也是永远等于一个特定值，因为 j-i 的值会有小于0的情况，所以我们在 j-i的基础上+n
代码：
#include
using namespace std;
int n,c[30],ch[30],che[30],a[30],cnt;
void dfs(int i)
{
int j,z;
if(i>n)
{
cnt++;
if(cnt<=3)
{
for(z=1;z<=n;z++) coutn;
dfs(1);
cout<<cnt;
return 0;
}
12.单词接龙——洛谷搜索题单1019
12.单词接龙——洛谷搜索题单1019
思路：先不论单词拼接，想法肯定是暴力深搜，简便快捷。
我们主要的问题肯定在于单词怎么判定拼接？这里我们需要使用一个叫 substr 的函数，用于比较两个字符串的某部分
主要用法如下
substr内第一个数字表示截取的位置，第二个表示截取个数，不是终止位置
题目是想比较，我们就取出来比较（注意截取个数不能大于len2）
len1的最后一个位置是len1-1，以此类推往前，而我们的截取数和位置有关系，所以有
if(str1.substr(len1-i,i)==str2.substr(0,i)) return str1+str2.substr(i,len2);
虽然str2.substr（i，len2）的len2大于剩余数量，但是没有影响
string类型是可以直接用+表示连接的
代码：
#include
#include
using namespace std;
string s[25];
int n,ans,mark[25];
string judge(string str1,string str2)
{
int i,len1=str1.size(),len2=str2.size();
for(i=1;i<len1&&ians) ans=str.size();
for(i=0;i>n;
for(i=0;i>s[i];
cin>>c;
for(i=0;i<n;i++)
{
if(s[i][0]==c)
{
mark[i]++;
dfs(s[i]);
mark[i]--;
}
}
cout<
最后
这篇题解涉及大部分洛谷官方搜索题解，下次更洛谷搜索题解就只更剩下部分了（狗头）
感觉这些题都挺好的，可以增加对基础搜索算法的理解（揣摩）
下次再见了🌹
本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://www.net2asp.com/fb4a0c569a.html
相关推荐
-
从错误中学习！腾讯AI Lab提出诱导大模型自身幻觉来消除幻觉
现有的大规模语言模型（LLM）在众多任务中取得了惊艳的效果，但它们在实际应用时仍然会出现生成与事实不符的内容。这种现象如今通常被称为“幻觉”。幻觉问题在真实场景中可能带来严重的后果…
-
Stable Diffusion教程(9) – AI视频转动漫
配套抖音视频教程：https://v.douyin.com/UfTcrcJ/ 安装mov2mov插件 打开webui 点击扩展->从网址安装 输入地址，然后点击安装 htt…
-
CES 2024丨引领变革，美格智能为智能终端带来生成式AI能力
作为电子行业的“风向标”，CES 2024（国际消费电子展）于1月9日至12日在美国拉斯维加斯举办。本届展会可谓是AI的盛宴，芯片、AI PC、智能家居、汽车科技、消费电子等领域与…
-
数据表中字段排序规则不一致（utf8mb4
环境： 数据库版本MySQL 8.0.32 报错： 在查询数据的时候返回以下错误 “(1267, \”Illegal mix of collations (…
-
GPTs | 如何构建私人AI助理
1 GPTs简介 GPTs是OpenAI推出的自定义GPT（Generative Pre-trained Transformers），允许用户构建自定义ChatGP…
-
[嵌入式AI从0开始到入土]11
[嵌入式AI从0开始到入土]嵌入式AI系列教程 注：等我摸完鱼再把链接补上 可以关注我的B站号工具人呵呵的个人空间，后期会考虑出视频教程，务必催更，以防我变身鸽王。 第1期 昇腾A…
-
Pytorch查看GPU信息
1、查看cuda是否可用：torch.cuda.is_available() >>> import torch >>> torch.cuda.i…
-
AI一键换衣，阿里Outfit Anyone来了，电商人的福音！
继谷歌推出Tryon Diffusion虚拟试穿后，国内的头部电商阿里也推出的Outfit Anyone虚拟试穿技术。该技术采用双流条件扩散模型，处理模特和服装数据…
-
第八章：AI大模型的安全与伦理8.2 模型安全8.2.1 对抗攻击与防御
1.背景介绍 随着人工智能技术的不断发展，AI大模型已经成为了我们生活中的一部分，它们在语音识别、图像识别、自然语言处理等方面的表现都越来越出色。然而，随着模型的复杂性和规模的增加…
-
智能工厂：AI在制造业的转型与升级
1.背景介绍 制造业是世界经济的重要驱动力，也是国家实现独立可持续发展的关键。然而，随着全球化的加剧、市场竞争的激烈和环境保护的需求，制造业面临着巨大的挑战。为了应对这些挑战，制造…
![[嵌入式AI从0开始到入土]11](/img/ea/7bf76b592e9948309ee12a01e743cb85.jpg)
