自动搬运

查看原文

来自洛谷，原作者为

	liwenjiedeluogu **

搬运于2025-08-24 23:13:01，当前版本为作者最后更新于2025-04-12 20:51:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

菜鸟第一次写题解，多多包涵！！!

这个题目的数据量很小，所以没必要去使用bfs，直接分情况讨论即可

一共两排数据，我们使用贪心的思想，只需要实现从左往右的过程中每个检测器相互连接即可，那么我们分三种情况讨论

第一种情况 |#|.| |:-:|:-:| |.||

当第一排的当前有检测器，而第一排的下一个没有检测器，且第二排的当前位没有检测器，我们不管第二排的下一个位置有没有检测器，我们只需要把第一排的下一个添加检测器便能够实现四个格子检测器的连通

第二种情况

与第一种情况类似，只是位置变了一下

第三种情况

这种情况相对复杂，我们不知道后面的情况，我们就只能从当前位置开始从第一排和第二排分别寻找再次出现 # 的位置 ，哪排先出现哪排的后面一个就变成 #

我们只需要判断这三种情况，没出现一次计数器加一，最后输出结果即可

这里面可以提前来找到最先出现 # 的位置 和最后出现 # 的位置，这样我们的循环会得到优化

希望能给你一点点小帮助

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int len = s1.size();
    int num = 0; // 计数器
    int l = len, r = 0;
    // 寻找第一出现和最后一个出现#的位置并记录
    for (int i = 0; i < len; i++)
    {
        if (s1[i] == '#' || s2[i] == '#')
        {
            l = min(l, i);
            r = max(r, i);
        }
    }
    for (int i = l; i < r; i++)
    {
        // 第一种情况的判断
        if (s1[i] == '#' && s1[i + 1] == '.' && s2[i] == '.')
        {
            num++;
            s1[i + 1] = '#';
            // cout << s1 << endl
            //      << s2 << endl
            //      << endl;
        }
        // 第二种情况的判断
        if (s1[i] == '.' && s2[i + 1] == '.' && s2[i] == '#')
        {
            num++;
            s2[i + 1] = '#';
            // cout << s1 << endl
            //      << s2 << endl
            //      << endl;
        }
        // 第三种情况的判断
        if (s1[i] == '#' && s2[i] == '#' && s2[i + 1] == '.' && s1[i + 1] == '.')
        {
            int p = i, q = i;
            for (int j = i + 1; j <= r; j++)
            {
                if (s1[j] == '#')
                {
                    p = j;
                    break;
                }
                if (s2[j] == '#')
                {
                    q = j;
                    break;
                }
            }
            if (p >= q)
            {
                s1[i + 1] = '#';
                num++;
            }
            else
            {
                s2[i + 1] = '#';
                num++;
            }
            // cout << s1 << endl
            //      << s2 << endl
            //      << endl;
        }
    }
    cout << num;
    return 0;
}