题解 CF1360E 【Polygon】
rui_er
2020-05-25 13:42:57
拿到这题一头雾水，找找规律。
按照游戏规则，一个数的右侧和下侧必须有数才可能被大炮发射到这里。
看到样例，发现如果去掉最后一行以及最后一列，剩余的所有 $1$ 的右侧或下侧的格子有 $1$，就是可以完成；反之不能。
大胆猜测：除了最右列与最下行，如果每个 $1$ 右侧或下侧都有 $1$，则可以完成；有一个 $1$ 右侧下侧均没有 $1$ 就不能完成。
考试时直接交了，没有证明正确性，发现 PP 了。现在口胡一个，不是特别严谨，可以画画图试着理解：
- 如果一个 $1$ 右侧有 $1$，可以通过左侧大炮发射过来。
- 如果一个 $1$ 下侧有 $1$，可以通过上方大炮发射过来。
- 最右列和最下行一定可以达到。
类似数学归纳法的思想，证明上面的猜测。
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
int T, n, a[55][55];
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
char c = getchar();
while(!isdigit(c)) c = getchar();
a[i][j] = c - '0';
}
}
bool book = true;
for(int i=1;i<n;i++) {
for(int j=1;j<n;j++) {
if(a[i][j] && !a[i][j+1] && !a[i+1][j]) {
book = false;
break;
}
}
if(!book) break;
}
if(book) puts("YES");
else puts("NO");
}
return 0;
}
```