搜索专题
目录P1219 八皇后 Checker Challenge（深搜）
- 思路：深搜当先行的每一个点，如果满足，就在该点处放置然后进入下一层深搜。终止条件是搜完最后一行。
- 注意点1：存的时候按行、列、左对角线、右对角线存，存该直线上是否有棋子；
- 注意点2：右对角线规律是相减为固定值，但是相减可能为负数，所以+n全部变为正再存
#include<bits/stdc++.h>
using namespace std;
int n,ct;
int row[100],col[100],ldia[100],rdia[100];
void print()
{
if(ct<3)
{
for(int i=1;i<n;i++)
{
cout<<row[i]<<" ";
}
cout<<row[n]<<endl;
}
ct++;
}
void dfs(int k) //k表示当前行
{
if(k>n)
{
print();
return;
}
for(int i=1;i<=n;i++) //遍历每一列
{
if(!col[i]&&!ldia[k+i]&&!rdia[k-i+n])
{
row[k]=i;
col[i]=1;
ldia[k+i]=1;
rdia[k-i+n]=1;
dfs(k+1);
row[k]=0;
col[i]=0;
ldia[k+i]=0;
rdia[k-i+n]=0;
}
}
}
int main()
{
cin>>n;
dfs(1);
cout<<ct<<'\n';
return 0;
}
P2392 kkksc03考前临时抱佛脚（还可用动规）
-
思路1（WA）：贪心，当前哪边脑子用时少就把这道题加在哪边。
-
错因：还要想办法让左右脑的差距最小
#include<bits/stdc++.h> using namespace std; int ans; int s[10]; int main() { for(int i=1;i<=4;i++) cin>>s[i]; for(int i=1;i<=4;i++) { int l=0,r=0,x; for(int j=1;j<=s[i];j++) { cin>>x; if(r<=l) r+=x; else l+=x; } ans+=max(l,r); } cout<<ans; return 0; } -
思路2：暴搜
#include<bits/stdc++.h> using namespace std; int ans,minn,l,r; int s[10],ts[10][100]; void search(int i,int k) //第i门课的第k个作业 { if(k>s[i]) { minn=min(minn,max(l,r)); return ; } l+=ts[i][k]; search(i,k+1); l-=ts[i][k]; r+=ts[i][k]; search(i,k+1); r-=ts[i][k]; } int main() { for(int i=1;i<=4;i++) cin>>s[i]; for(int i=1;i<=4;i++) { l=0,r=0; minn=5000; for(int j=1;j<=s[i];j++) { cin>>ts[i][j]; } search(i,1); ans+=minn; } cout<<ans; return 0; }
P1135 奇怪的电梯（bfs）
-
注意！！！广搜细节！！！
#include<bits/stdc++.h> using namespace std; const int N=1000; int n,a,b,step; int k[N],vis[N]; int main() { cin>>n>>a>>b; for(int i=1;i<=n;i++) cin>>k[i]; bool f=0; queue<int> q; q.push(a); vis[a]=1; while(!q.empty()) { int kk=q.size(); //这里！！！一定要把size先存一下！！！不然q.size()就是变化的！！！！！ for(int i=0;i<kk;i++) { int x=q.front(); q.pop(); if(x==b) { f=1; break; } if(x-k[x]>=1&&!vis[x-k[x]]) { vis[x-k[x]]=1; q.push(x-k[x]); } if(x+k[x]<=n&&!vis[x+k[x]]) { vis[x+k[x]]=1; q.push(x+k[x]); } } if(f) break; step++; } if(!f) { cout<<-1<<'\n'; } else cout<<step<<'\n'; return 0; }
P2895 Meteor Shower S（二维bfs）
-
记录每一个格子被流行砸的时间是哪一个时刻，在该时刻前贝西就能走。
-
二维：用两个队列分别存x和y
#include<bits/stdc++.h> using namespace std; const int N=5e4+10; int m,x,y,t,step; bool f=0; int timel[310][310],vis[310][310]; int xx[6]={0,0,0,1,-1}; int yy[6]={0,1,-1,0,0}; int main() { for(int i=0;i<310;i++) { for(int j=0;j<310;j++) timel[i][j]=-1; } cin>>m; while(m--) { cin>>x>>y>>t; for(int i=0;i<5;i++) { if((x+xx[i]>=0&&y+yy[i]>=0)&&(t<timel[x+xx[i]][y+yy[i]]||timel[x+xx[i]][y+yy[i]]==-1)) { timel[x+xx[i]][y+yy[i]]=t; } } } queue<int> q[2]; q[0].push(0); q[1].push(0); vis[0][0]=1; while(!q[0].empty()&&!q[1].empty()) { int sz=q[0].size(); for(int i=0;i<sz;i++) { int nxx=q[0].front(),nyy=q[1].front(); q[0].pop(); q[1].pop(); if(timel[nxx][nyy]==-1) { f=1; break; } for(int i=1;i<5;i++) { int nx=nxx+xx[i]; int ny=nyy+yy[i]; if(nx>=0&&ny>=0&&(step<timel[nx][ny]-1||timel[nx][ny]==-1)&&!vis[nx][ny]) { vis[nx][ny]=1; q[0].push(nx); q[1].push(ny); } } } if(f) break; step++; } if(f) cout<<step; else cout<<"-1"; return 0; }
P1036 选数(深搜)
-
思路：
-
疑问：如果数据是5 3 3 7 12 19 19，输入是3，是3 7 19，3 7 19，3 19 19，但是3 7 19会被算两次？
#include<bits/stdc++.h> using namespace std; int ans,n,k; int a[100]; bool isprime(int x) { if(x==0||x==1) return false; if(x==2) return true; for(int i=2;i<sqrt(x);i++) { if(x%i==0) return false; } return true; } //b是当前选了几个数 //c是现在和为几 //d表示当前加的从哪个数开始 void dfs(int b,int c,int d) { if(b==k) { if(isprime(c)) { ans++; } return ; } for(int i=d;i<n;i++) { dfs(b+1,c+a[i],i+1); } return; } int main() { cin>>n>>k; for(int i=0;i<n;i++) { cin>>a[i]; } // sort(a,a+n); dfs(0,0,0); cout<<ans<<endl; return 0; }
P1433 吃奶酪（还需用状态压缩优化）
-
这里只用了dfs+剪枝
#include<bits/stdc++.h> using namespace std; int n; double ans=0x7fffffff; double x[50],y[50],vis[50],dis[100][100]; void dfs(int now,double js,double sum) { if(sum>ans) return ;//剪枝 if(js==n) { ans=min(ans,sum); return; } for(int i=1;i<=n;i++) { if(!vis[i]) { vis[i]=1; //sum+=dis[now][i];注意这个地方不能这么写，不然for循环后面sum的值就加多了。如果要这么写，下面写回溯就要加一个sum-=dis[now][i] dfs(i,js+1,sum+dis[now][i]); vis[i]=0; } } return; } int main() { cin>>n; x[0]=0; y[0]=0; for(int i=1;i<=n;i++) { cin>>x[i]>>y[i]; } for(int i=0;i<=n;i++) { for(int j=0;j<=n;j++) { dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); } } dfs(0,0,0); printf("%.2f",ans); return 0; }
P1019 [NOIP2000 提高组] 单词接龙
-
注意点1：开头的字母已经定了，所以“龙”只能往后接，不用考虑接到前面的问题。
-
注意点2：要使“龙”最长，应取最小重叠部分
#include<bits/stdc++.h> using namespace std; string s[50]; int n,ans; int vis[50]; int canlink(string s1,string s2) { int len1=s1.length(); int len2=s2.length(); int sum=0; for(int i=1;i<min(len1,len2);i++) { bool f=1; for(int j=0;j<i;j++) { if(s1[len1-i+j]!=s2[j]) f=0; } if(f) return i; } return 0; } void dfs(string snow,int lnow) //当前的字符串，当前的长度 { ans=max(lnow,ans); for(int i=0;i<n;i++) { if(vis[i]<2&&canlink(snow,s[i])) { vis[i]++; dfs(s[i],lnow+s[i].length()-canlink(snow,s[i]));//youwenti vis[i]--; } } } int main() { cin>>n; for(int i=0;i<=n;i++) cin>>s[i]; for(int i=0;i<n;i++) { if(s[i][0]==s[n][0]&&vis[i]<2) { vis[i]++; dfs(s[i],s[i].length()); vis[i]--; } } cout<<ans; return 0; }
P1101 单词方阵（dfs）
- 思路：找到y就从各个方向进dfs往下搜，只要有一个不对就return false。
#include<bits/stdc++.h>
using namespace std;
int n;
int vis[150][150];
string s[150];
string es="yizhong";
int xx[10]={1,1,0,-1,-1,-1,0,1};
int yy[10]={0,1,1,1,0,-1,-1,-1};
bool dfs(int x,int y,int de,int js)
{
js++;
if(js==7)
return true;
int nx=x+xx[de];
int ny=y+yy[de];
if(nx>=0&&nx<n&&ny>=0&&ny<n&&s[nx][ny]==es[js])
{
if(dfs(nx,ny,de,js))
{
vis[nx][ny]=1;
return true;
}
else
return false;
}
else
return false;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>s[i];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(s[i][j]==es[0])
for(int k=0;k<8;k++)
{
if(dfs(i,j,k,0))
{
vis[i][j]=1;
}
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(vis[i][j])
cout<<s[i][j];
else
cout<<"*";
}
cout<<endl;
}
return 0;
}
P2404 自然数的拆分问题
-
要用数组存一下每种情况，每次搜到底输出
#include<bits/stdc++.h> using namespace std; int n,ans; int a[15]; void dfs(int now,int sum,int js) { if(sum>n) return ; if(sum==n) { ans++; for(int i=0;i<js-1;i++) { cout<<a[i]<<"+"; } cout<<a[js-1]<<endl; return ; } for(int i=now;i<=n-1;i++) { a[js]=i; dfs(i,sum+i,js+1); a[js]=0; } return; } int main() { cin>>n; dfs(1,0,0); return 0; }
P1596 Lake Counting S（dfs）（染色）
- 经典的数水洼问题
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
char mp[110][110];
int xx[10]={1,1,1,0,0,-1,-1,-1};
int yy[10]={1,-1,0,1,-1,0,1,-1};
void dfs(int x,int y)
{
for(int i=0;i<8;i++)
{
int nx=x+xx[i];
int ny=y+yy[i];
if(nx>=0&&nx<n&&ny>=0&&ny<m&&mp[nx][ny]=='W')
{
mp[nx][ny]='.';
dfs(nx,ny);
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>mp[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(mp[i][j]=='W')
{
dfs(i,j);
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}
P1162 填涂颜色（染色）
- 如果被1包围，则0一定挨不到边界，所以->把挨不到边界的0变成2 -> 把挨得到边界的0变成3，和被包围的0区分开
#include<bits/stdc++.h>
using namespace std;
int n;
int mp[50][50];
int xx[5]={1,-1,0,0};
int yy[5]={0,0,1,-1};
void dfs(int x,int y)
{
for(int i=0;i<4;i++)
{
int nx=x+xx[i];
int ny=y+yy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&mp[nx][ny]==0)
{
mp[nx][ny]=3;
dfs(nx,ny);
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>mp[i][j];
}
}
for(int i=1;i<=n;i++)
{
if(mp[i][1]==0)
{
dfs(i,1);
}
if(mp[n][i]==0)
{
dfs(n,i);
}
if(mp[i][n]==0)
{
dfs(i,n);
}
if(mp[1][i]==0)
{
dfs(1,i);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mp[i][j]==3)
{
cout<<0<<" ";
}
else if(mp[i][j]==0)
cout<<"2 ";
else
cout<<mp[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
P1825 Corn Maze S（bfs）
- 最短路径问题：应该用广搜。最开始用深搜超时了。
#include<iostream>
#include<queue>
using namespace std;
const int N=350;
struct point{
int x;
int y;
int t;
};
queue<point> que;
char a[N][N];
bool vis[N][N];
int n,m;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int sx;
int sy;
void goto_another(int &nx,int &ny,int k)//goto_another函数用于寻找另一个传送门，nx、ny代表当前点的坐标，记得要加上取地址符'&'，因为每当贝西踏入一个传送门，它就会立即被传送至另一个传送门，不能在原地停留
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]==a[nx][ny]&&(i!=nx||j!=ny))//如果a[i][j]这个点的是一个与a[nx][ny]相同的传送门，并且a[i][j]与a[nx][ny]不是同一个点
{
nx=i;//改变当前坐标，将贝西强行移动至另一个传送门处
ny=j;
return ;//告辞
}
}
}
}
int main()
{
cin>>n>>m;
string s;
for(int i=1;i<=n;i++)
{
cin>>s;//由于输入奇奇怪怪地没有空格，于是乎窝便使用字符串读入
for(int j=1;j<=m;j++)
{
a[i][j]=s[j-1];
if(a[i][j]=='@')//获取起点坐标
{
sx=i;
sy=j;
}
}
}
que.push((point){sx,sy,0});
while(!que.empty())
{
point f=que.front();
que.pop();
if(a[f.x][f.y]=='=')
{
cout<<f.t;
return 0;
}
if(a[f.x][f.y]>='A'&&a[f.x][f.y]<='Z')//特判部分，如果当前点是一个传送门，那么就传送至另一个传送门
{
goto_another(f.x,f.y,f.t);
}
for(int i=0;i<=3;i++)
{
int nx=f.x+dx[i];
int ny=f.y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&!vis[nx][ny])
{
vis[nx][ny]=true;
que.push((point){nx,ny,f.t+1});
}
}
}
return 0;
}