总体情况
这一周学习了最近公共祖先，并且了解了dijkstra的模板，也在比赛中补了一些最短路的题，然后图的专题还没开始刷，这一周把搜索和搜索剪枝的专题差不多写完了，对dfs的各种代码实现更加深入了，但是搜索是一大块内容，涉及的题目多样经典。我想着后面对这些题再慢慢分个类，不然真正比赛的时候还是没有办法写出来。
联通块类的搜索
模拟战役
点击查看代码
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
#define all(v) v.begin(),v.end()
int dx[8]={0,0,1,-1,1,-1,1,-1};
int dy[8]={1,-1,0,0,1,-1,-1,1};
int m,dri;//dri为司机拥有的联通块数目
char c[10][105];//地图
bool vis[10][105];//标记
int cnt[105*105];//存齐齐每个连通块大炮的数目，因为要用来贪心
bool ck1(int x,int y)
{
return x>=1&&x<=4&&y>=1&&y<=m;
}
bool ck2(int x,int y)
{
return x>4&&x<=8&&y>=1&&y<=m;
}
//计算了司机的联通块数目，也就是一个大炮被攻击时产生的连锁反应
void bfs1(int i,int j)
{
vis[i][j]=1;
queue<pii> q;
q.push({i,j});
while(!q.empty())
{
int x=q.front().first,y=q.front().second;
q.pop();
for(int i=0;i<8;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(ck1(nx,ny)&&!vis[nx][ny]&&c[nx][ny]=='*')
{
q.push({nx,ny});
vis[nx][ny]=1;
}
}
}
}
//计算齐齐的连通块数目，和连通块数目里大炮的个数
int bfs2(int i,int j)
{
int res=0;
vis[i][j]=1;
queue<pii>q;
q.push({i,j});
while(!q.empty())
{
int x=q.front().first,y=q.front().second;
res++;//要放在这里，不然会少算
q.pop();
for(int i=0;i<8;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(ck2(nx,ny)&&!vis[nx][ny]&&c[nx][ny]=='*'){
//res++;//错了
vis[nx][ny]=1;
q.push({nx,ny});
}
}
}
return res;
}
void solve()
{
cin>>m;
for(int i=1;i<=8;i++){
for(int j=1;j<=m;j++) cin>>c[i][j];
}
for(int i=1;i<=4;i++){
for(int j=1;j<=m;j++)
{
if(c[i][j]=='*'&&!vis[i][j]) bfs1(i,j),dri++;
}
}
int p=0;
for(int i=5;i<=8;i++)
{
for(int j=1;j<=m;j++){
if(c[i][j]=='*'&&!vis[i][j]) {
cnt[++p]=bfs2(i,j);
}
}
}
/* cout<<dri<<" "<<p<<endl;
for(int i=1;i<=p;i++) cout<<cnt[i]<<" ";
cout<<endl;*/
sort(cnt+1,cnt+p+1);
if(dri>p) {
cout<<-1<<endl;
return ;
}
int ans=0;
for(int i=dri;i<=p;i++) ans+=cnt[i];
cout<<ans;
}
signed main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t=1;
//cin>>t;
while(t--)
{
solve();
}
}
三维的bfs
Jelly
点击查看代码
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
#define all(v) v.begin(),v.end()
int dx[]={0,1,0,-1,0,0};
int dy[]={1,0,-1,0,0,0};
int dz[]={0,0,0,0,1,-1};
int n;
char c[105][105][105];
bool vis[105][105][105];
int foot[105][105][105];
//三维bfs模版题
bool ck(int x,int y,int z)
{
return x>=1&&x<=n&&y>=1&&y<=n&&z>=1&&z<=n;
}
typedef struct{
int aa;
int bb;
int cc;
}three;
int ans;
int bfs(int i,int j,int k)
{
queue<three>q;
vis[i][j][k]=1;
q.push({i,j,k});
while(!q.empty())
{
int x=q.front().aa,y=q.front().bb,z=q.front().cc;
q.pop();
for(int i=0;i<6;i++)
{
int nx=x+dx[i],ny=y+dy[i],nz=z+dz[i];
if(ck(nx,ny,nz)&&!vis[nx][ny][nz]&&c[nx][ny][nz]!='*')
{
q.push({nx,ny,nz});
vis[nx][ny][nz]=1;
foot[nx][ny][nz]=foot[x][y][z]+1;
}
}
}
return foot[n][n][n];
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++) cin>>c[i][j][k];
ans= bfs(1,1,1)+1;//记得+1，虽然题目说第一个不算，但是不知道为啥+1就过了
if(ans!=1) cout<<ans;
else cout<<-1;
}
signed main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t=1;
//cin>>t;
while(t--)
{
solve();
}
}
涉及到无限的搜索
送外卖
点击查看代码
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
#define all(v) v.begin(),v.end()
int dx[]={0,1,0,-1,0,0};
int dy[]={1,0,-1,0,0,0};
int dz[]={0,0,0,0,1,-1};
bool vis[100005],st[100005];
vector<pii>ve;
char ans[100005];
int n;
int fla;//看有没有符合的字符串
bool dfs(int x,int deep)
{
if(x<0||x>n-1) return 0;
if(x==n-1)
{
ans[deep]='\0';
return 1;
}
if(vis[x])
{
st[x]=1;
return 0;
}
vis[x]=1;
//走第一条路
if(dfs(x+ve[x].first,deep+1))
{
ans[deep]='a';
if(st[x]) fla=1;//说明在一条路径中出现了死循环
return true;
}
//走第二条路
if(dfs(x+ve[x].second,deep+1))
{
ans[deep]='b';
if(st[x]) fla=1;
return true;
}
return 0;
}
//dfs找到的结果自然就是最小的
void solve()
{
cin>>n;
vector<int>a(n),b(n);
for(auto &t:a) cin>>t;
for(auto &t:b) cin>>t;
for(int i=0;i<n;i++)
{
ve.push_back({a[i],b[i]});
}
if(dfs(0,0)){
if(fla) cout<<"Infinity!";
else cout<<ans;
}else
cout<<"No solution!";
}
signed main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t=1;
//cin>>t;
while(t--)
{
solve();
}
}
经典数独dfs
数独挑战