codeforces E. Polygon_codeforces.polygon白屏

题目

题意：

图中的大炮，每次都可以向这个方向射出$1$到尽头（尽头指的是最大范围或者碰到$1$的时候），问给你一个这样的图，是否可以在使用这些大炮的情况下，出现这种图。

思路：

我们可以发现，对于左边界，下边界肯定是可以出现的，因为只要第一个吐出来的，肯定就是到达边界的了，之后就是中间的了，那么我们的左边或者下边一定要有一个是要$1$的，不然没有办法把这个$1$卡在中间，所以遍历一遍，我们就要看除了左边界，下边界之外的是否符合上述上述条件。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <cctype>
using namespace std;
typedef long long ll;
typedef vector<int> veci;
typedef vector<ll> vecl;
typedef pair<int, int> pii;
template <class T>
inline void read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return ;
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1:1;
    ret = (c == '-') ? 0:(c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return ;
}
inline void out(int x) {
    if (x > 9) out(x / 10);
    putchar(x % 10 + '0');
}
const int maxn = 60;
char s[maxn][maxn];
bool check(int x, int y) {
    return ((s[x + 1][y] == '1') || (s[x][y + 1] == '1'));
}
int main() {
    int t, n;
    read(t);
    while (t--) {
        read(n);
        for (int i = 1; i <= n; i++) {
            scanf("%s", s[i] + 1);
        }
        for (int j = 1; j <= n + 1; j++) {
            s[n + 1][j] = '1';
            s[j][n + 1] = '1';
        }
        bool flag = false;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (s[i][j] == '1' && !check(i, j)) {
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }
        if (flag) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67