有一种叫做 Berland crossword 的拼图游戏。这个拼图由 \(n\) 行 \(n\) 列组成,你可以将里面的一些格子涂成黑色。现在给出 \(T\) 个这样的拼图,每个拼图都含有如下限制:
问是否有满足如上限制的拼图(不需要输出方案)。
数据范围:\(2\leqslant n\leqslant 100\),\(0\leqslant u,r,d,l\leqslant n\),\(1\leqslant T\leqslant 10^3\)。
第二题还是一样的暴力,只不过可能和其他那些直接暴力枚举 \(16\) 种情况的不太一样,这里讲讲。
首先,我们可以想到,如果 \(u=n\),那么第一列和第 \(n\) 列都至少有 \(1\) 个黑色格子,\(d=n\) 同理;如果 \(r=n\),那么第一行和第 \(n\) 行都至少有一个黑色格子,\(l=n\) 同理。
另外还有一种比较特殊的情况,就是当上面的四个数中的某些数 \(=n-1\)。如果 \(u=n-1\),那么第一列和第 \(n\) 列中的一列至少会有 \(1\) 个黑色格子,\(d=n-1\) 同理;如果 \(r=n-1\),那么第一行和第 \(n\) 行中的一行至少会有 \(1\) 个黑色格子,\(l=n-1\) 同理。
于是,我们不妨先设出所有的 \(u,r,d,l\) 所在的行列在输入限制下的最小黑色格子数。先把所有的 \(=n\) 的情况所影响的行列的最小黑色格子数加 \(1\),然后对于 \(=n-1\) 的情况,我们看当前还有那些行列的最小黑色格子数小于输入限制,就把那个行列的最小黑色格子数加 \(1\)(如果两个行或者两个列当前的最小黑色格子数都小于输入限制,随便加进去哪一个行列都行)。最后再来判断是否超过了输入限制即可。
如果上面的文字你并没有听懂,可以参考一下下面的代码实现。
int n, u, r, d, l, limit[7], num[7];
int main() {
MT {
memset(limit, 0, sizeof(limit));
memset(num, 0, sizeof(num));
n = Rint, u = Rint, r = Rint, d = Rint, l = Rint;
if(u >= n - 1) limit[1] = u - (n - 2);
if(r >= n - 1) limit[2] = r - (n - 2);
if(d >= n - 1) limit[3] = d - (n - 2);
if(l >= n - 1) limit[4] = l - (n - 2);
num[1] += (limit[2] == 2) + (limit[4] == 2), num[2] += (limit[1] == 2) + (limit[3] == 2), num[3] += (limit[2] == 2) + (limit[4] == 2), num[4] += (limit[1] == 2) + (limit[3] == 2);
if(limit[1] == 1) {(num[2] < r ? num[2] : num[4])++;}
if(limit[2] == 1) {(num[1] < u ? num[1] : num[3])++;}
if(limit[3] == 1) {(num[2] < r ? num[2] : num[4])++;}
if(limit[4] == 1) {(num[1] < u ? num[1] : num[3])++;}
puts((u >= num[1] && r >= num[2] && d >= num[3] && l >= num[4]) ? "YES" : "NO");
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章