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
68
69
70
71
| #include <cstdio>
#include <algorithm>
using namespace std;
const int N = 210, inf = 1e9;
const int dx[] = {0, -1, 1, 0, 0}, dy[] = {0, 0, 0, -1, 1};
struct Node
{
int w, d;
} q[N];
int hd, tl;
bool avai[N][N];
int n, m, sx, sy, k, ans, f[N][N];
bool read()
{
char c = getchar();
while (c != '.' && c != 'x')
c = getchar();
return c == '.';
}
bool inside(int x, int y)
{
return x > 0 && y > 0 && x <= n && y <= m;
}
void solve(int x, int y, int t, int d)
{
hd = 1, tl = 0;
for (int i = 1; inside(x, y); i++, x += dx[d], y += dy[d])
{
if (!avai[x][y])
{
hd = 1, tl = 0;
continue;
}
while (hd <= tl && q[tl].w + i - q[tl].d <= f[x][y])
tl--;
if (hd <= tl && i - q[hd].d > t)
hd++;
q[++tl] = (Node){f[x][y], i};
f[x][y] = q[hd].w + i - q[hd].d;
ans = max(ans, f[x][y]);
}
}
int main()
{
scanf("%d%d%d%d%d", &n, &m, &sx, &sy, &k);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
avai[i][j] = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
f[i][j] = -inf;
f[sx][sy] = 0;
for (int s, t, d; k; k--)
{
scanf("%d%d%d", &s, &t, &d);
if (d == 1)
for (int i = 1; i <= m; i++)
solve(n, i, t - s + 1, d);
else if (d == 2)
for (int i = 1; i <= m; i++)
solve(1, i, t - s + 1, d);
else if (d == 3)
for (int i = 1; i <= n; i++)
solve(i, m, t - s + 1, d);
else if (d == 4)
for (int i = 1; i <= n; i++)
solve(i, 1, t - s + 1, d);
}
printf("%d", ans);
return 0;
}
|