BZOJ3208 花神的秒题计划Ⅰ

2015.01.20 09:37 Tue| 0 visits oi_2015| 2015_刷题日常| Text

Solution

真·逗逼题 + 读入题。滑雪加强版。记忆化搜索水过。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 705

bool v[N][N];
int n, m, a[N][N], f[N][N];
int dx[5] = {0, 1, 0, 0,-1},
    dy[5] = {0, 0, 1,-1, 0};

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch-'0'; ch = getchar(); }
    return x * f;
}

int dfs(int x, int y)
{
    if (f[x][y]) return f[x][y];
    f[x][y] = 1;
    for (int i = 1; i <= 4; ++i)
        if (v[x + dx[i]][y + dy[i]] && a[x + dx[i]][y + dy[i]] < a[x][y])
            f[x][y] = max(f[x][y], dfs(x + dx[i], y + dy[i]) + 1);
    return f[x][y];
}

int main()
{
    cin >> n;
    memset(v, 0, sizeof v);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            a[i][j] = read(), v[i][j] = true;
    cin >> m;
    char opt[2]; int x, y, z, w, ans;
    for (int i = 1; i <= m; ++i)
    {
        scanf("%s", opt);
        switch (opt[0])
        {
            case 'Q' :
            ans = 0;
            memset(f, 0, sizeof f);
            for (int j = 1; j <= n; ++j)
                for (int k = 1; k <= n; ++k)
                    if (v[j][k])
                        ans = max(ans, dfs(j, k));
            cout << ans << endl;
            break;
            case 'C' :
            x = read(); y = read(); z = read();
            a[x][y] = z;
            break;
            case 'S' : case 'B' :
            x = read(); y = read(); z = read(); w = read();
            for (int j = x; j <= z; ++j)
                for (int k = y; k <= w; ++k)
                    v[j][k] = (opt[0] != 'S');
            break;
        }
    }
}