- 1#include "iostream"2#include "cstdio"3#include "cstring"4#include "string"5#include "algorithm"6 using namespace std;
- 7 const int maxn = 200 + 10;
- 8 char g[maxn][maxn];
- 9 int f[maxn][maxn];
- 10 int n,
- m,
- x,
- y,
- k,
- l,
- r,
- res;
- 11 pair < int,
- int > q[maxn],
- tmp;
- 12 int dx[] = {
- 0,
- -1,
- 1,
- 0,
- 0
- },
- dy[] = {
- 0,
- 0,
- 0,
- -1,
- 1
- };
- 13 bool judge(int x, int y) {
- 14
- if (x >= 1 && x <= n && y >= 1 && y <= m) return true;
- 15
- return false;
- 16
- }
- 17 void solve(int x, int y, int d, int len) {
- 18 l = r = 0;
- 19
- for (int i = 0; judge(x, y); i++, x += dx[d], y += dy[d]) {
- 20
- if (g[x][y] == 'x') l = r = 0;
- 21
- else {
- 22 tmp.first = f[x][y],
- tmp.second = i;
- 23
- while (l1].first + (i - q[r - 1].second) <= tmp.first) r--;
- 24 q[r++] = tmp;
- 25
- while (llen) l++;
- 26 f[x][y] = q[l].first + (i - q[l].second);
- 27 res = max(res, f[x][y]);
- 28
- }
- 29
- }
- 30
- }
- 31 int main() 32 {
- 33 scanf("%d%d%d%d%d", &n, &m, &x, &y, &k);
- 34
- for (int i = 1; i <= n; i++) 35 scanf("%s", g[i] + 1);
- 36 memset(f, 0x80, sizeof(f));
- f[x][y] = 0;
- 37
- for (int i = 1, s, e, d, len; i <= k; i++) {
- 38 scanf("%d%d%d", &s, &e, &d);
- len = e - s + 1;
- 39
- if (d == 1) for (int j = 1; j <= m; j++) solve(n, j, 1, len);
- 40
- else if (d == 2) for (int j = 1; j <= m; j++) solve(1, j, 2, len);
- 41
- else if (d == 3) for (int j = 1; j <= n; j++) solve(j, m, 3, len);
- 42
- else for (int j = 1; j <= n; j++) solve(j, 1, 4, len);
- 43
- }
- 44 printf("%d\n", res);
- 45
- }
来源: http://www.bubuko.com/infodetail-2063303.html