CF1586C-Omkar and Determination

我以为它是图论,谁又能想到这又是一道贪心呢。

题意概括

给一个n×m的迷宫,*.表示空路径,X表示存在不能通过的障碍。人在迷宫中行动时只能往左或往上。我们构建一个01图a,$a_{i,j}$​表示从迷宫的(i,j)点出发,若能走出迷宫则记其值为1,否则记其值为0。(n<1e6,m<1e6,nm<1e6)

再给出q次询问,每次循环有两个数x1、x2,询问能否通过原迷宫从x1到x2的子迷宫的01图判断出子迷宫哪里有石头。可以回答YES,否则回答NO。

题目分析

这道题其实更适合作为A题。

对于任何一个位置,如果01图在这里的值为0,那么要么这个点本身就是石头,要么这个点往上一格、往左一格均不能走出迷宫(即均为0)。也就是说,如果有一个点不能走出迷宫,且其左边的一个点、上边的一个点也不能走出迷宫,我们就没法判断这个点是否存在石头。

那么对于每一个子迷宫,我们只需要构建一张01图,然后判断其中是否存在这样的结构即可:

1
2
0 0
0

由于n和m的范围较大,因此我们选择使用预处理前缀和的方式进行即可。

代码

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
#include <bits/stdc++.h>
#define int long long
#define maxn 1000200
using namespace std;

inline int read() {
register char c = getchar();
register int f = 1, _ = 0;
while (c > '9' || c < '0')
f = (c == '-') ? -1 : 1, c = getchar();
while (c <= '9' && c >= '0')
_ = (_ << 3) + (_ << 1) + (c ^ 48), c = getchar();
return _ * f;
}
int n, m;
string s[maxn];
int a[maxn];

signed main() {
n = read(), m = read();
for (register int i = 1; i <= n; i++) {
cin >> s[i];
s[i] = " " + s[i];
}
for (register int i = 1; i <= m; i++) {
for (register int j = 2; j <= n; j++) {
if (s[j][i - 1] == 'X' && s[j - 1][i] == 'X')
a[i] = 1;
}
a[i] += a[i - 1];
}
int q = read();
while (q--) {
int x1 = read(), x2 = read();
if (a[x2] - a[x1])
puts("NO");
else
puts("YES");
}
return 0;
}