JZTXT

《算法竞赛》---搜索

发布时间 2024-01-10 17:18:16作者: 月下~观星

搜索

二叉树搜索

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;
}