算法总结——深度优先搜索进阶

· · 算法·理论

由于深度优先搜索的原理和构造过于简单，我们直接开始讲题。

T1 海战

本题是联通块的加强版，难点在于判断船是否相撞。

思路：

设 maxx,minx 表示当前块最大和最小的 x 坐标， maxy,miny 表示当前块最大和最小的 y 坐标。那么假设该块是是个矩形，那么 maxx-miny+1 就是其在 x 坐标上的边的长度， maxy-miny+1 就是其在 y 坐标上的边的长度，那么它的面积就是 (maxx-miny+1)\times (maxy-miny+1) 。我们可以在扫描块时开一个计数器，每到一个联通的方格就记一个数，同时记录以上的四个变量。一个块扫描完成后，我们看看计数器的值，也就是该块的实际面积是否等于用 maxx,maxy,minx,miny 算出的面积，如果相等说明这是一个矩形，反之亦然。

代码：

#include <bits/stdc++.h>
using namespace std;

int n,m,maxx,maxy,minx,miny,cnt = 0,ans = 0;
char mp[1005][1005];

void dfs(int x,int y)
{
    if(x < 1 || y < 1 || x > n || y > m) return;
    if(mp[x][y] == '.') return;
    mp[x][y] = '.';
    maxx = max(maxx,x);
    maxy = max(maxy,y);
    minx = min(minx,x);
    miny = min(miny,y);
    cnt++;
    dfs(x+1,y);
    dfs(x,y+1);
    dfs(x-1,y);
    dfs(x,y-1);
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            cin >> mp[i][j];
        }
    }
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            if(mp[i][j] == '#')
            {
                maxx = -1e9;
                maxy = -1e9;
                minx = 1e9;
                miny = 1e9;
                cnt = 0;
                dfs(i,j);
                if(cnt == (maxx-minx+1)*(maxy-miny+1))
                {
                    ans++;
                }else
                {
                    cout << "Bad placement.";
                    return 0;
                }
            }
        }
    }
    cout << "There are " << ans << " ships.";
    return 0;
}

T2 [NOIP2004 普及组] 火星人

本题在全排列模板代码上加几行就过了。

思路：

我们可以让全排列的起点不是字典序最小的那个，而是输入的排列顺序。\ 我们可以记一个 flag ，如果其没有被标记， for 循环的 i 改成 a_i （对应题目输入数据的第三行），生成一个全排列后就把它标上。再开个计数器，每生成一个全排列就记一个数，一等于 m 就输出那次生成全排列的结果。

代码：

#include <bits/stdc++.h>
using namespace std;

long long n,m,a[10005],cnt = 0,box[10005];
bool vis[10005],flag = 0;

void dfs(int steps)
{
    if(steps > n)
    {
        flag = 1;
        if(cnt == m)
        {
            for(int i = 1;i <= n;i++) cout << box[i] << ' ';
            exit(0);
        }
        cnt++;
        return;
    }
    for(int i = 1;i <= n;i++)
    {
        if(flag == 0) i = a[steps];
        if(vis[i] == 0)
        {
            vis[i] = 1;
            box[steps] = i;
            dfs(steps+1);
            vis[i] = 0;
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> a[i];
    dfs(1);
    return 0;
}

T3 [USACO23JAN] Air Cownditioning II B

思路：

也是全排列，只是每次改都要改一个区间，可以用差分优化。

代码：

#include <bits/stdc++.h>
using namespace std;

int n,m,l[15],r[15],p[15],a[15],mini = 1e9,box[105],mubiao[105];

void dfs(int steps,int money)
{
    if(steps > m)
    {
        for(int i = 1;i <= 100;i++) if(box[i] < mubiao[i]) return;
        mini = min(mini,money);
        return;
    }
    for(int i = l[steps];i <= r[steps];i++) box[i] += p[steps];
    dfs(steps+1,money+a[steps]);
    for(int i = l[steps];i <= r[steps];i++) box[i] -= p[steps];
    dfs(steps+1,money);
}

int main(void)
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        int s,t,c;
        cin >> s >> t >> c;
        for(int j = s;j <= t;j++) mubiao[j] += c;
    }
    for(int i = 1;i <= m;i++) cin >> l[i] >> r[i] >> p[i] >> a[i];
    dfs(1,0);
    cout << mini;
    return 0;
}

T4 狗哥玩木棒

思路：

用暴搜将木棒分配给正方形的 4 条边，直接这么写肯定会超时，需要加剪枝优化。\ 既然每根木棒都要用，那么如果合法，每边长度必定等于四分之一个所有木棒长度之和。所以，我们可以先算出所有木棒的长度之和 s ，如果 s 不是 4 的倍数，直接输出“no”；在搜索中，如果其中某一组的长度大于了 \frac{1}{4}s，直接剪掉。

代码：

#include <bits/stdc++.h>
using namespace std;

int T,n,a[25],flag = 0,ac_len;

void dfs(int steps,int b1,int b2,int b3,int b4)
{
    if(b1 > ac_len || b2 > ac_len || b3 > ac_len || b4 > ac_len) return;
    if(steps > n)
    {
        if(b1 == b2 && b2 == b3 && b3 == b4 ) flag = 1;
        return;
    }
    if(flag==1) return;
    dfs(steps+1,b1+a[steps],b2,b3,b4);
    dfs(steps+1,b1,b2+a[steps],b3,b4);
    dfs(steps+1,b1,b2,b3+a[steps],b4);
    dfs(steps+1,b1,b2,b3,b4+a[steps]);
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--)
    {
        cin >> n;
        ac_len = 0;
        for(int i = 1;i <= n;i++)
        {
            cin >> a[i];
            ac_len += a[i];
        }
        flag = 0;
        if(ac_len % 4 == 0)
        {
            ac_len /= 4;
            sort(a+1,a+n+1);
            dfs(1,0,0,0,0);
        }
        if(flag) cout << "yes\n";
        else cout << "no\n";
    }
    return 0;
}

T5 [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins

这题用二进制枚举存答案会比较方便。

思路：

用二进制枚举每种饲料是否选择，一定要注意需要输出的是字典序最小的答案。

代码：

#include <bits/stdc++.h>
using namespace std;

int n,xuyao[35],m,a[25][35],have[35],mini = 0,mincnt = 1e9;

bool check(void)
{
    for(int i = 1;i <= n;i++) if(xuyao[i] > have[i]) return 0;
    return 1;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> xuyao[i];
    cin >> m;
    for(int i = 1;i <= m;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            cin >> a[i][j];
        }
    }
    for(int i = 1;i < (1<<m);i++)
    {
        int cnt = 0;
        memset(have,0,sizeof(have));
        for(int j = 0,p = 1<<(m-1);j < m;j++,p>>=1)
        {
            if(i&p)
            {
                cnt++;
                for(int k = 1;k <= n;k++) have[k] += a[j+1][k];
            }
        }
        if(check() && mincnt >= cnt)
        {
            mincnt = cnt;
            mini = i;
        }
    }
    cout << mincnt << ' ';
    for(int j = m-1;j >= 0;j--)
    {
        if(mini>>j&1) cout << m-j << ' ';
    }
    return 0;
}

T6 增进感情

这题面也是无语了。

思路：

和kkksc03考前临时抱佛脚差不多，都是选和不选的问题，只是这题需要多判一下两人是否能在一起。

代码：

#include <bits/stdc++.h>
using namespace std;

int n,v,a[35],b[35],mini = 1e9;

void dfs(int steps,int suma,int sumb)
{
    if(steps > n)
    {
        if(suma+sumb >= v) mini = min(mini,abs(suma-sumb));
        return;
    }
    dfs(steps+1,suma+a[steps],sumb+b[steps]);
    dfs(steps+1,suma,sumb);
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> v;
    for(int i = 1;i <= n;i++) cin >> a[i] >> b[i];
    dfs(1,0,0);
    if(mini != 1e9) cout << mini;
    else cout << -1;
    return 0;
}