搜索专题（未完）
搜索做题总结
前言：
因为搜索一直被众OIer称为万能算法——很多题都能用搜索得部分分，所以...所以...嗯，还是重新再刷一遍搜索的题，找找感觉吧！希望在之后的大小比赛考试中能够发挥出来quq
搜索提单——从基础到提高（未完）：
- 基础
-- 洛谷P1451 求细胞个数
-- 洛谷P1141 01迷宫
-- 洛谷P1683 入门 （此“入门”非彼“入门”，虽然都还挺简单的）
-- 洛谷P1157 组合的输出
-- 洛谷P1036 选数
-- 洛谷P1443 马的遍历
-- 洛谷P1746 离开中山路
-- 洛谷P2372 yyy2015c01挑战算周长
（题目有点长..我这个蒟蒻读了两遍题才读懂QAQ但是题很简单）
其实这些题很多都是有相似的地方的，而这些相似的地方就是搜索的基础。我们可以把这里作为突破口，然后清晰思路，更利于编程。
常见的搜索基础类型：“搜索求联通块”、“n个数选k个数”
- 提高
-- 洛谷P2360 地下城主
（虽然标签是普及-，但是我认为比马的遍历那些题会难一点？大概还是因为我蒻）
-- 洛谷P2298 Mzc和男家丁的游戏
-- 洛谷P1332 血色先锋队
-- 洛谷P1434 滑雪
-- 洛谷P1019 单词接龙
-- 洛谷P1032 字串变换
-- 洛谷P3956 棋盘
（这道题我用广搜没有搞出来，就是太菜，然后使用了WS同学的深搜，这里就推荐一篇他的题解：棋盘 题解）
部分题目思路：
- 基础
-- 求细胞个数、01迷宫、入门、yyy2015c01挑战算周长：“搜索求联通块”
-- 组合的输出、选数：DFS，“n个数选k个数”
-- 马的遍历、离开中山路：BFS求最短距离
- 提高
-- 地下城主：三维搜索+求最短距离，注意一下数组是先层再行再列（我栽在这1hQAQ），后面给出该题的代码
-- Mzc和男家丁的游戏、血色先锋队：求最短距离
-- 滑雪、单词接龙、字串变换、棋盘：之后会给出代码
部分题目代码（题解以后再补充qwq）：
- 求细胞个数
#include <bits/stdc++.h> using namespace std; int n,m,ans; char a[105][105]; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0};
inline void bfs(int x,int y) { a[x][y]='0'; for(register int i=0;i<4;i++) { int xx=x+dx[i]; int yy=y+dy[i]; if(xx>n||xx<1||yy>m||yy<1||a[xx][yy]=='0') continue; bfs(xx,yy); } }
int main() { scanf("%d%d",&n,&m); for(register int i=1;i<=n;i++) { for(register int j=1;j<=m;j++) { cin>>a[i][j]; } } for(register int i=1;i<=n;i++) { for(register int j=1;j<=m;j++) { if(a[i][j]!='0') { ans++; bfs(i,j); } } } printf("%d",ans); return 0; }
- 选数
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,r,sum,ans,num[5000001];
inline bool check(int tot) {
for(register int i=2;i*i<=tot;i++) {
if(tot%i==0) return false;
}
return true;
}
inline void dfs(int now,int k) {
for(register int i=k;i<=n;i++) {
sum+=num[i];
if(now==r) {
if(check(sum)) ans++;
}
else dfs(now+1,i+1);
sum-=num[i];
}
}
int main() {
scanf("%d%d",&n,&r);
for(register int i=1;i<=n;i++) {
scanf("%d",&num[i]);
}
dfs(1,1);
printf("%d",ans);
return 0;
}- 马的遍历
#include <bits/stdc++.h> using namespace std; int n,m,sx,sy,pd[4005][4005],ans[4005][4005]; int dx[8]={1,2,2,1,-1,-2,-2,-1}; int dy[8]={2,1,-1,-2,-2,-1,1,2};
struct node { int x,y,st; } q[160005];
inline void bfs(int xx,int yy) { pd[xx][yy]=1; int front=1,tail=1; q[front].x=xx; q[front].y=yy; q[front].st=0; while(front<=tail) { for(register int i=0;i<8;i++) { int xs=q[front].x+dx[i]; int ys=q[front].y+dy[i]; if(xs>=1&&xs<=n&&ys>=1&&ys<=m&&pd[xs][ys]==0) { tail++; q[tail].x=xs; q[tail].y=ys; q[tail].st=q[front].st+1; ans[xs][ys]=q[tail].st; pd[xs][ys]=1; } } front++; } }
int main() { memset(ans,-1,sizeof(ans)); scanf("%d%d%d%d",&n,&m,&sx,&sy); ans[sx][sy]=0; bfs(sx,sy); for(register int i=1;i<=n;i++) { for(register int j=1;j<=m;j++) { printf("%-5d",ans[i][j]); } puts(""); } return 0; }
- 地下城主
```cpp
#include <bits/stdc++.h>
using namespace std;
int L,R,C,sx,sy,sh,ex,ey,eh,sum,ans;
char a[31][31][31];
int dx[6]={0,1,0,-1,0,0};
int dy[6]={1,0,-1,0,0,0};
int dh[6]={0,0,0,0,1,-1};
struct node {
int x,y,h,st;
} q[100001];
inline void bfs(int xx,int yy,int hh) {
a[hh][xx][yy]='#'; //一定要注意先层再行再列！
int front=1,tail=1;
q[front].x=xx;
q[front].y=yy;
q[front].h=hh;
q[front].st=0;
while(front<=tail) {
for(register int i=0;i<6;i++) {
int xs=q[front].x+dx[i];
int ys=q[front].y+dy[i];
int hs=q[front].h+dh[i];
if(xs>=1&&xs<=R&&ys>=1&&ys<=C&&hs>=1&&hs<=L&&a[hs][xs][ys]!='#') {
tail++;
q[tail].x=xs;
q[tail].y=ys;
q[tail].h=hs;
q[tail].st=q[front].st+1;
if(xs==ex&&ys==ey&&hs==eh) {
printf("Escaped in %d minute(s).",q[tail].st);
return ;
}
a[hs][xs][ys]='#';
}
}
front++;
}
puts("Trapped!");
}
int main() {
scanf("%d%d%d",&L,&R,&C);
for(register int i=1;i<=L;i++) {
for(register int j=1;j<=R;j++) {
for(register int k=1;k<=C;k++) {
cin>>a[i][j][k];
if(a[i][j][k]=='S') {
sx=j;
sy=k;
sh=i;
}
if(a[i][j][k]=='E') {
ex=j;
ey=k;
eh=i;
}
}
}
}
bfs(sx,sy,sh);
return 0;
}- 血色先锋队
#include <bits/stdc++.h> using namespace std; int n,m,a,b,pd[5005][5005],ans[5005][5005]; int x,y; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0};
struct node { int x,y,st; }q[2500005];
inline void bfs(int tot) { int front=1,tail=tot; while(front<=tail) { for(register int i=0;i<4;i++) { int xx=q[front].x+dx[i]; int yy=q[front].y+dy[i]; if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&pd[xx][yy]==0) { pd[xx][yy]=1; tail++; q[tail].x=xx; q[tail].y=yy; q[tail].st=q[front].st+1; ans[xx][yy]=q[tail].st; } } front++; } }
int main() { scanf("%d%d%d%d",&n,&m,&a,&b); for(register int i=1;i<=a;i++) { scanf("%d%d",&x,&y); q[i].x=x; q[i].y=y; q[i].st=0; pd[x][y]=1; ans[x][y]=0; } bfs(a); for(register int i=1;i<=b;i++) { scanf("%d%d",&x,&y); printf("%d\n",ans[x][y]); } return 0; }
- 滑雪
```cpp
#include <bits/stdc++.h>
using namespace std;
int c,r,sum=0,a[101][101],f[101][101];
int dx[5]={0,0,-1,0,1};
int dy[5]={0,1,0,-1,0};
inline void dfs(int x,int y) {
f[x][y]=1;
int tot=0,ans=1;
for(int i=1;i<=4;i++) {
int xx=x+dx[i];
int yy=y+dy[i];
if(xx>=1&&xx<=r&&yy>=1&&yy<=c&&a[xx][yy]>a[x][y]) {
if(f[xx][yy]==0) {
dfs(xx,yy);
}
f[x][y]=max(f[x][y],f[xx][yy]+1);
}
}
}
int main() {
cin>>r>>c;
for(int i=1;i<=r;i++) {
for(int j=1;j<=c;j++) {
cin>>a[i][j];
}
}
for(int i=1;i<=r;i++) {
for(int j=1;j<=c;j++) {
if(f[i][j]==0) dfs(i,j);
sum=max(sum,f[i][j]);
}
}
cout<<sum;
return 0;
}- 单词接龙
#include <bits/stdc++.h> using namespace std; char str[101][101],st; //str储存单词，st是开头字母 int jl[101],n,tot=0,maxx=0,l[101],n2; //jl储存单词长度；tot储存当前最长长度，maxx储存结果最长长度；L数组标记单词是否用过 void dfs(int x,int y) { //x是当前单词，y是上一个单词 if(tot>maxx) maxx=tot; //把最大值赋给maxx for(int i=1;i<=n2;i++) { //每个单词有两次机会 if(x==1) { if(str[i][0]!=st) continue; //这个单词的开头不等于给定的开头字母，跳出0 l[i]=1; //标记这个单词已用过 tot+=jl[i]; //把单词的长度累加到tot中 dfs(x+1,i); //判断下一个单词 l[i]=0; //回溯，重置为0 tot-=jl[i]; //恢复长度，长度减等于单词长度 } if(l[i]==1) continue; //如果这个单词用过，跳出 int c=1,k=jl[y]-1;//c是单词重合的长度，k等于上一个单词长度减1 char a[1001]={'\0'},b[1001]={'\0'}; while(c<=jl[i]&&c<jl[y]) { //重合长度不超过当前单词长度且小于上一个单词长度 strncpy(a,str[i],c); //单词从左向右赋值c个字母到A数组 strncpy(b,&str[y][k--],c); //上一个单词从k到开头复制c个字母到B数组 if(strcmp(a,b)==0) { //判断两个字符串是否相等 tot+=jl[i]-c; //长度加等于单词长度减去重合长度 l[i]=1; //标记为用过 dfs(x+1,i); //判断下一个单词 tot-=jl[i]-c; //回溯 l[i]=0; break; //重合部分越小，龙越大 } c++; //重合长度++ } } } int main() { cin>>n; n2=2*n; //因为每个单词可以用两次 for(int i=1;i<=n;i++) { //输入单词 cin>>str[i]; jl[i]=strlen(str[i]); //jl储存每个单词的长度 } for(int i=n+1;i<=n2;i++) { //第二遍 strcpy(str[i],str[i-n]); //一个单词可用两遍 jl[i]=jl[i-n]; //jl[i]储存这个单词两次的长度 } cin>>st; //给定开头的字母 dfs(1,0); //处理第一个单词 cout<<maxx; //输出最长长度 return 0; } -
字串变换
#include<bits/stdc++.h> using namespace std; string a,b; //字符串A与字符串B string sa[8],sb[8]; //存放6种转换方式 map<string,int> map1; //用map存放已经宽搜过的字符串，用来判重剪枝（否则会超时） int l; //有l种转换方式 queue<string> q; //存放转换出来的字符串 queue<int> bb; //存放当前转换出来的字符串已经使用的步数 int bfs() { int i,j,k,m,n; string s,ss; while (q.empty()==0&&q.front()!=b&&bb.front()<=10) { //当还能继续转换且没转换出字符串B且步数也没有超出10步时进行宽搜 if (map1[q.front()]==1) { //剪枝：如果当前字符串已经宽搜过了,就弹出,进入下一次循环. q.pop(); bb.pop(); continue; } map1[q.front()]=1; //记录下该字符串 for (i=1; i<=l; i++) { //循环出每一种转换方式 s=q.front(); //将S赋值为当前要操作的字符串 while (1) { //找出子串sa[i]的所有位置 m=s.find(sa[i]); //在S里查找子串sa[i]的第一次出现位置 if (m==-1) break; //如果全找出来(找不到)了,就结束循环 ss=q.front(); //将SS赋值为当前要操作的字符串 ss.replace(m,sa[i].size(),sb[i]); //在SS中用子串sb[i]替换掉S里第一次出现的子串sa[i] q.push(ss); //将转换后的SS压入队列 bb.push(bb.front()+1); //将转换后的SS已经使用的步数压入队列 s[m]='~'; //将S里子串sa[i]的第一次出现位置随便换成另一种无关的字符,这样就可以查找到S里子串sa[i]的下一个出现位置 } } q.pop(); //将操作过的字符串弹出队列 bb.pop(); //操作过的字符串已经用过的步数一块弹出 } if (q.empty()==1||bb.front()>10) return -1;//没法再进行宽搜,或者超出步数,就返回-1 else return bb.front(); //否则,就是找到了,便返回最少使用步数 } int main() { int i,j,k,m,n; cin>>a>>b; //读入字符串A与字符串B l=1; while (cin>>sa[l]>>sb[l]) l++; //读入转换方式 l--; //l初始值为1,所以要减1,才能表示转换方式的数量 if (l==0&&a!=b) { //若果没有转换方式且A也不等于B,直接输出"NO ANSWER!"(其实这步可以不要) cout<<"NO ANSWER!"; return 0; } q.push(a); //将字符串A压入队列 bb.push(0); //将初始步数0压入队列 k=bfs(); //宽搜 if (k==-1) { //返回-1说明NO ANSWER! cout<<"NO ANSWER!"; return 0; } cout<<k; //输出最小步数 }