P11667 [USACO25JAN] Astral Superposition B题目描述注意本题的时间限制为 4 秒通常限制的 2 倍。Bessie 正在使用她超酷的望远镜拍摄夜空中所有星星的照片。她的望远镜能够拍摄到一张N×NN \times NN×N1≤N≤10001 \leq N \leq 10001≤N≤1000的星星照片其中每个像素是一颗星星或者空旷的天空。每颗星星可由恰好一个像素表示并且没有两颗不同的星星位于同一像素内。一夜之间一些奇怪的事情发生在了天空中的星星之上。每颗星星要么消失要么向右移动AAA像素并且向下移动BBB像素0≤A,B≤N0 \leq A,B \leq N0≤A,B≤N。如果一颗星星消失或移动超出照片边界它将不再出现在第二张照片中。Bessie 在星星移动位置之前和之后拍了照片但在 Mootoshop 中进行了一些实验后她不小心将一张照片叠加到了另一张上。现在她可以在两张照片都是天空的位置看到白色white像素在星星仅存在于恰好一张照片的位置看到灰色gray像素而在两张照片中都有星星的位置看到黑色black像素。Bessie 同时记得没有新的星星移动入第二张照片的范围从而她的第一张照片包含了夜空中所有的星星。对于TTT1≤T≤10001 \leq T \leq 10001≤T≤1000个独立的测试用例给定最终的照片求在移动事件发生之前天空中星星的最小可能数量。如果不存在星星的排列可以产生给定的最终照片输出−1-1−1。输入格式输入的第一行包含TTT以下为TTT个测试用例。每个测试用例的第一行包含NNNAAABBB。以下NNN行每行表示叠加后的照片的一行。从上到下第iii行由一个字符串ci,1ci,2…ci,Nc_{i,1}c_{i,2}\dots c_{i,N}ci,1​ci,2​…ci,N​表示其中ci,j∈{W,G,B}c_{i,j} \in \{\texttt{W,G,B}\}ci,j​∈{W,G,B}分别表示颜色为白色灰色以及黑色。输入保证所有测试用例的N2N^2N2之和不超过10710^7107。输出格式对于每一个测试用例输出移动之前存在的星星的最小数量或−1-1−1表示不可能。输入输出样例 #1输入 #11 3 0 0 WWB BBB GGG输出 #17输入输出样例 #2输入 #23 5 1 2 GWGWW WGWWW WBWGW WWWWW WWGWW 3 1 1 WWW WBW WWW 3 1 0 GGB GGW WWW输出 #24 -1 4说明/提示样例解释在样例 #1 中没有移动发生。第一张照片如下. 表示天空* 表示星星..* *** ***第二张照片中最下方一行的星星都消失了如下..* *** ...这是产生叠加后照片的唯一方式所以初始时星星的最小可能数量为777。对于样例 #2在第一个测试用例中初始时至少有444颗星星。如果我们令(r,c)(r,c)(r,c)表示从上到下第rrr行和从左到右第ccc列的交点一种可能性是它们最初位于(1,1)(1,1)(1,1)(3,2)(3,2)(3,2)(2,2)(2,2)(2,2)和(1,3)(1,3)(1,3)。除了位于(2,2)(2,2)(2,2)的星星消失之外其他所有星星都移动了。在第二个测试用例中在给定的移动方式下没有任何初始照片中的星星排列可以产生中间的黑色像素。在第三个测试用例中初始时至少有444颗星星。一种可能性是它们最初位于(1,1)(1,1)(1,1)(1,2)(1,2)(1,2)(1,3)(1,3)(1,3)和(2,1)(2,1)(2,1)。在第二张照片中原先位于(1,1)(1,1)(1,1)的星星消失了原先位于(1,3)(1,3)(1,3)的星星移出了照片边界。其他两颗星星向右移动了111像素。子任务测试点 3AB0AB0AB0。测试点 4-7A1A1A1B0B0B0N≤10N\le 10N≤10。测试点 8-9A1A1A1B0B0B0。测试点 10-12没有额外限制。C实现#includebits/stdc.husingnamespacestd;intT,n,a,b,ans;charg[1010][1010];boolflag,vis[1010][1010];intmain(){ios::sync_with_stdio(0);cin.tie(0);cinT;while(T--){ans0;flag0;memset(vis,0,sizeof(vis));memset(g,0,sizeof(g));cinnab;for(inti0;in;i)cing[i];for(inti0;in;i){for(intj0;jn;j){if(g[i][j]B){vis[i][j]1;if(ibjag[i-b][j-a]!W)vis[i-b][j-a]1;else{flag1;break;}}elseif(g[i][j]G)if(!(ibjag[i-b][j-a]!Wvis[i-b][j-a]))vis[i][j]1;}if(flag){cout-1\n;break;}}if(!flag){for(inti0;in;i)for(intj0;jn;j)if(vis[i][j])ans;coutans\n;}}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容