搜索
二叉树搜索
bfs搜索二叉树---p98
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n;
char a[100000];
struct node
{
char value;
int lson,rson;
}tree[N];
int idx=1;
int newnode(char val)
{
tree[idx].value=val,tree[idx].lson=0,tree[idx].rson=0;//
return idx++;
}
void insert(int father,int tmp,int l)
{
if(l==0)tree[father].lson=tmp;
else tree[father].rson=tmp;
}
int buildtree()
{
cin>>n;
char h;
cin>>h; a[1]=newnode(h);
for(int i=2;i<=n;i++)
{
char g;cin>>g;a[i]=newnode(g);
}
bool is=true;
for(int i=2;i<=n;i++)
{
if(is)
{insert(a[i-1],a[i],0);is=false;}
else {insert(a[i-1],a[i],1);is=true;}
}
return a[1];
}
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
int root=buildtree();
queue<int>q;
q.push(root);
while(q.size())
{
int tmp=q.front();
cout<<tree[tmp].value<<' ';
q.pop();
if(tree[tmp].lson!=0)q.push(tree[tmp].lson);
if(tree[tmp].rson!=0)q.push(tree[tmp].rson);
}
return 0;
}
连通性判断(bfs,dfs,并查集)
注意搜索的是会被全部淹没的连通块
全球变暖(bfs)-----p106--蓝桥杯
//输入案例
7
.......
.##....
.##....
....##.
..####.
...###.
.......
#include <bits/stdc++.h>
using namespace std;
int n,ans;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
char a[1010][1010];
bool vis[1010][1010];
bool g;
struct node{
int x,y;
};
void bfs(int x,int y)
{
g=false;
queue<node>q;
q.push({x,y});
vis[x][y]=true;
while(q.size())
{
int mx=q.front().x,my=q.front().y;
int res=0;
q.pop();
for(int i=0;i<4;i++)
{
int nx=mx+dx[i],ny=my+dy[i];
if(nx<1||nx>n||ny<1||ny>n||a[nx][ny]=='.')continue;
if(vis[nx][ny]){res++;continue;}
res++;
q.push({nx,ny});
vis[nx][ny]=true;
}
if(res==4){g=true;}
}
}
int main()
{
// 请在此输入您的代码
ios::sync_with_stdio(false);cin.tie();cout.tie();
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(a[i][j]=='#'&&!vis[i][j])
{
bfs(i,j);
if(!g)ans++;
}
}
cout<<ans;
return 0;
}
注意 bool元素df递归时候被后面false覆盖问题
全球变暖(dfs版本)
#include<bits/stdc++.h>
using namespace std;
int res,n;
char a[1010][1010];
bool df;
bool vis[1010][1010];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void dfs(int x,int y)
{
vis[x][y]=true;
for(int i=0;i<4;i++)
{
if(a[x+dx[i]][y+dy[i]]=='.')break;
if(i==3)df=true;//这样写才可以防止写出false
}
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(!vis[nx][ny]&&a[nx][ny]=='#')
dfs(nx,ny);
}
}
int main()
{
ios::sync_with_stdio(false);cin.tie();
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(a[i][j]=='#'&&!vis[i][j])
{
df=false;
dfs(i,j);
if(!df)res++;
}
}
cout<<res;
return 0;
}
剪枝
bfs去重
八数码问题分支---跳蚱蜢(p110)---蓝桥杯642
#include<bits/stdc++.h>
using namespace std;
int bfs(string s)
{
string end="087654321";
unordered_map<string,int>dist;
queue<string>q;
q.push(s);
dist[s]=0;
while(q.size())
{
auto t=q.front();q.pop();
int r=dist[t];
if(t==end)return r;
int x=t.find('0');
for(int i=-2;i<=2;i++)//四种方向，
{
int nx=(x+i+9)%9;//代码核心，将圆盘位置化为直线位置
if(nx<0||nx>8||nx==x)continue;//特判超出和本身
swap(t[nx],t[x]);
if(!dist[t])
{
dist[t]=r+1;
q.push(t);
}
swap(t[nx],t[x]);
}
}
return -1;
}
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
string s="012345678";
cout<<bfs(s);
return 0;
}
dfs 可行性剪枝+最优性剪枝--洛谷5194
前缀和进行最优性剪枝
#include<bits/stdc++.h>
using namespace std;
int n,c;
long long a[1010],s[1010];
long long ans;
void dfs(int u,long long sum)
{
if(sum>c)return;
if(s[u]+sum<=c)//如果当前sum+s[u]可以全拿直接拿走，回溯看看之前能不能拿
{
ans=max(ans,sum+s[u]);
return;
}
if(sum+a[u]<=c)dfs(u-1,sum+a[u]);//如果当前元素能拿拿走并且向下搜索
dfs(u-1,sum);//拿不了，就向下搜素
}
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
cin>>n>>c;
for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];}
dfs(n,0);//倒着查肯定搜素快一点利于使用前缀和剪枝
cout<<ans;
return 0;
}
dfs 可行性剪枝p112(poj 3278)
dfs 奇偶剪枝----p114(hdu 1010)
flood fill模型
1v312 ( Red and Black )
普通的连通块问题
#include<iostream>
#include<cstring>
using namespace std;
int n, m;
char a[21][21];
bool vis[21][21];
int cnt;
int d[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
void dfs(int x, int y)
{
vis[x][y] = true;
cnt++;
for (int i = 0; i < 4; i++)
{
int nx = x + d[i][0], ny = y + d[i][1];
if (nx > 0 && nx <= n && ny > 0 && ny <= m && !vis[nx][ny] && a[nx][ny] == '.')
{
dfs(nx, ny);
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(); cout.tie();
while (1)
{
cin>>n>>m;
if(n==0&&m==0)break;
int x, y;
swap(n,m);
for (int i = 1; i <= n;i++)
for (int j = 1; j <= m;j++)
{
cin >> a[i][j];
if (a[i][j] == '@')
x = i, y = j;
}
dfs(x, y);
cout << cnt << endl;
memset(vis,false,sizeof vis);
cnt = 0;
}
return 0;
}
The Wedding Juicer--p122(poj 2227)
优先队列处理边界
从周围堵中央
每次处理边界最矮的往内部扩散--(因为最矮的不会妨碍后面)
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int n, m;
const int N = 310;
typedef long long ll;
#define fr first
#define se second
ll a[N][N];
bool vis[N][N];
typedef pair<int, int>PII;
int d[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
ll cnt;
struct cmp {
bool operator()(pair<pair<int,int>,ll> a,pair<pair<int, int>, ll> b) {
return a.second > b.second;
}
};
void bfs()
{
priority_queue<pair<pair<int, int>, ll >, vector<pair<pair<int, int>, ll>>,cmp>q;
cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (i == 1 || j == 1 || i == n || j == m)
{
q.push({ {i,j },a[i][j] });
vis[i][j] = true;
}
}
while (q.size())
{
int h = q.top().se, x = q.top().fr.fr, y = q.top().fr.se; q.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + d[i][0], ny = y + d[i][1];
ll hh = a[nx][ny];
if (nx <= 0 || nx > n || ny <= 0 || ny > m || vis[nx][ny])continue;
if (hh < h)
{
cnt += h - hh;
// cout << a[nx][ny] << ' ' << hh << '\n';
hh = h;
}
q.push({ {nx,ny},hh });
vis[nx][ny] = true;
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(); cout.tie();
cin >> n >> m;
swap(n, m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
bfs();
cout << cnt << endl;
return 0;
}
填涂颜色---p123(洛谷1162)
将所有0先全部染成2
dfs从四周到中央搜索，与上题目寻找所有储水单位一样，从边缘i1||j1||jn||in搜索为2的点,染成0，最后输出矩阵
#include<bits/stdc++.h>
using namespace std;
const int N=31;
bool vis[N][N];
int a[N][N];
int n,m;
int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void dfs(int x,int y)
{
if(a[x][y]==2)
a[x][y]=0;
for(int i=0;i<4;i++)
{
int nx=x+d[i][0],ny=y+d[i][1];
if(nx<1||nx>n||ny<1||ny>n||!a[nx][ny]||a[nx][ny]==1)continue;
dfs(nx,ny);
}
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
if(!a[i][j])a[i][j]=2;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if((i==1||j==1||i==n||j==n)&&a[i][j]==2)
dfs(i,j);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<a[i][j]<<' ';
cout<<endl;
}
return 0;
}