题解：P11667 [USACO25JAN] Astral Superposition B

题解：P11667 [USACO25JAN] Astral Superposition B

发一篇之前在luogu上没发出去的题解（考USACO时的考场思路+代码）

题意理解

每颗星星要么消失，要么向右移动 A 像素，并且向下移动 B 像素 （0≤A,B≤N）

也就是行（下文用 i 表示）+ b ，列（下文用 j 表示）+ a 的意思。

现在，她可以在两张照片都是天空的位置看到白色（ white ）像素，在星星仅存在于恰好一张照片的位置看到灰色（ gray ）像素，而在两张照片中都有星星的位置看到黑色（ black ）像素。

十分明显，即重叠的照片中每一个像素都有三种颜色： W , G , B 类别如下：

1. W ：两张照片的这个位置都没有出现星星

2. G ：只有一张照片中这个位置出现了星星

3. B ：两张照片中的这个位置都出现了星星

这道题的时间限制（居然有 4 秒！）表明：直接挨个检查就行啦！

思路

思路非常易懂。

先设置好所有的变量和二维数组，用 ans 来统计最初可能的星星数量，并且边输入边输出（每个样例输入完后直接输出）。

检查两张照片叠加后的所有像素：
优先检查是‘ B ’的，因为没有新的星星移动入第二张照片的范围，所以如果出现了‘ B ’，应是第一张照片中的一个‘ G ’移至这个位置，并且第一张照片中的在此位置的‘ G ’消失或移走。所以，‘ B ’在移动前不可以出边界或在移动前的位置没有星星（为‘ W '）

如果出现以上任意一种情况（出边界或没有星星），则 ans=-1 （没有可能性，注意 ans=-1 后要果断break检查的循环并直接输出，开始下一个样例）

检查完‘ B ’后，开始检查重叠的照片中的‘ G ’。
检查‘ G ’的规则很简单：如果在移动前的位置 （i-b，j-a） 没有星星（为‘ W ’）或者移动前的位置出了边界或者它可以移动到一个‘ B ’上（这个条件是因为‘ B ’的条件，如果它是由一个‘ G ’移过来的话，那么它就不可能组成‘ B ’，所以‘ G ’一旦可以组成‘ B ’就要果断去加），那么它就是第一张照片中必定有的一个星星， ans++ 。如果不满足以上条件，那么将此‘ G ’刷成‘ W ’（因为它是由一个星星移动而成的，所以不是最初的星星之一，主要是因为一个星星不能移动两次，刷成‘ W ’以免出现误判。）

还有就是如果不移动 （ a0&&b0 ） 要特判。

Code

#include<iostream>
#include<string>
using namespace std;const int MAXN=1005;
int t;
string s[MAXN];
//一系列定义void clear(){for (int i=0;i<MAXN;i++){s[i].clear();}
}//清空s数组，因为每一次都要用int main(){cin>>t;//依题意，输入样例数量while(t--){int n,a,b;cin>>n>>a>>b;int ans=0;for(int i=0;i<n;i++){cin>>s[i];}//输入for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(s[i][j]=='B'){//先判断Bif(i-b<0||j-a<0||s[i-b][j-a]=='W'){//如果移动前的位置出边界或没有星星就不合理ans=-1;break;//如果发现不合理就退出}ans++;//如果合理，就ans++。因为在第一张照片中在这个位置有一个‘G’}}if(ans==-1)break;//如果发现不合理就退出*2}if(ans==-1){cout<<ans<<endl;continue;//如果发现不合理就下一个样例}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(s[i][j]=='G'){//接下来检查‘G’if(i-b<0||j-a<0||s[i-b][j-a]=='W'||(a==0&&b==0)||((i+b<n&&j+a<n)&&s[i+b][j+a]=='B')){//刚才说的三个条件ans++;}else{s[i][j]='W';//如果是移过来的就刷成‘W’}}}}cout<<ans<<endl;//普普通通的输出clear();//清空数组，下一个样例还要用}return 0;//完美于此
}

本代码并不能保证最优，但是也是尽力了（考场代码）。