自动搬运

查看原文

来自洛谷，原作者为

	chzhh_111 退是死，前是生||坐标：FJ，现初三，已学 OI 两年||比赛等级分上不了2000，不改签

搬运于2025-08-24 23:09:18，当前版本为作者最后更新于2025-02-06 13:38:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我是用通过模拟来判断是否存在可行的方案并记录数量。

我们首先用两个数组来记录 $\texttt{G}$ 和 $\texttt{B}$ 的位置。

接下来我们再用两个布尔数组 $p1$ 和 $p2$ 来分别记录来，这一个位置的星星是属于第一张照片还是属于第二张照片，当然，如果这个位置为黑色，那么这个位置的两个布尔数组都是 $true$。

然后我们再用两个变量 $sum1$ 和 $sum2$ 来分别记录第一张星星的数量和第二张星星的数量（实际上应该只要用一个就行了）。

我们可以十分肯定地确认，如果照片的某一个位置为 $\texttt{B}$，那么这个位置肯定就有第一张照片的星星和第二张照片的星星。所以如果一个位置为 $\texttt{B}$，那么我们可以从此位置向上移动 $B$ 个单位，再向左移动 $A$ 个单位，看一下移动后的位置：

• 第一种情况，如果它已经在这个照片外，那么肯定没有合法方案。因为题目已经说了，第一个照片当中包含了所有的星星，而且第二张照片的星星必须得从第一张照片的星星转移过来。所以就可以判断，如果出现这样的情况，就不存在合法方案。

• 第二种情况就是这个位置为 $\texttt{W}$，同理这样也没有合法方案。

因此如果出现以上两种情况，就直接输出 $-1$。否则，我们就将移动后的位置和当今位置的 $p1$ 标记成 $true$，将当今位置的 $p2$ 也标记成 $true$，$sum1$ 和 $sum2$ 也随之改变。

接下来我们再考虑 $\texttt{G}$ 的位置：

• 第一种情况，如果这个位置我们之前已经标记过了就不用再判断了。

• 第二种情况，继续判断从此位置向上移动 $B$ 个单位，再向左移动 $A$ 个单位后的位置。如果它在照片外面或者这个位置为 $\texttt{W}$，则当今位置为第一张照片的星星，而且从此位置向下移动 $B$ 个单位，再向右移动 $A$ 个单位的位置如果为 $\texttt{G}$，且这个位置的 $p1$ 为 $false$，则这个位置为第二张照片的星星。

• 第三种情况，如果从此位置向上移动 $B$ 个单位，再向左移动 $A$ 个单位后的位置在照片内，且该位置的 $p1$ 为 $true$，那这个位置就为第二张照片的星星。

我们再进行相应的统计。

最后输出 $sum1$ 就是答案了。

代码部分：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1001;
int T,n,A,B,sum1,sum2;char a[N][N];
bool p1[N][N],p2[N][N];
struct dian{
    int x,y;
};
vector<dian>b,g;
void clean()
{
    memset(p1,0,sizeof(p1));
    memset(p2,0,sizeof(p2));
    sum1=sum2=0;
}
bool solve()
{
    for(dian i:b)
    {
        int x=i.x,y=i.y;
        if(x-B<1||y-A<1||a[x-B][y-A]=='W') return 0;
        sum1+=!p1[x-B][y-A];
        p1[x-B][y-A]=1;
        sum1+=!p1[x][y];
        p1[x][y]=1;
        p2[x][y]=1;
        sum2++;
    }
    for(dian i:g)
    {
        int x=i.x,y=i.y;
        if(p1[x][y]||p2[x][y]) continue;
        if(x-B<1||y-A<1||!p1[x-B][y-A])
        {
            p1[x][y]=1;
            sum1++;
            if(x+B<=n&&y+A<=n&&a[x+B][y+A]=='G'&&!p1[x+B][y+A])
            {
                p2[x+B][y+A]=1;
                sum2++;
            }
        }
        else if(x-B>=1&&y-A>=1&&p1[x-B][y-A]) p2[x][y]=1,sum2++;
    }
    return 1;
}
signed main()
{
    scanf("%lld",&T);
    while(T--)
    {
        clean();
        scanf("%lld%lld%lld",&n,&A,&B);
        b.clear(),g.clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%s",a[i]+1);
            for(int j=1;j<=n;j++)
            {
                if(a[i][j]=='B') b.push_back((dian){i,j});
                if(a[i][j]=='G') g.push_back((dian){i,j});
            }
        }
        if(solve()) printf("%lld\n",sum1);
          else printf("-1\n");
    }
    return 0;
}