题解：P11667 [USACO25JAN] Astral Superposition B

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