11083: 【原1083】足球比赛

题目

题目描述

author: 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1083

Description

二哥所在的班级参加了在计科岛上举办的足球比赛。

由于计科岛上气候恶劣，同二哥一起来的队员都病倒了。只有身体强壮的二哥可以参加比赛。此时此刻，二哥一个人，正面对着对方的10:0:0阵型。

但他知道：这一刻，他不是一个人在战斗！！！！

为了赢得比赛，他决定将比赛拖入加时赛，再拖入点球大战，然后用他精湛的脚法获胜。

为此，他要做一个长达120分钟的带球。

二哥不愧是一名优秀的足球运动员，经过精确的计算，二哥已经找到了一个能躲避所有对手的方法。

确切的说：二哥发现，如果将比赛时间分成K个时间区间，在每个时间区间里，二哥只能选择每秒向固定的方向移动或者停在原地，如果向其他方向移动就会有被抢断的风险。（假设二哥每秒钟可以移动一个单位）。计科岛的比赛场地上有许多的障碍物。二哥碰到障碍物就会摔倒。因此，如果沿着当前的方向，在下一秒将会移动到障碍物所在的位置，那么这一秒二哥必须停在原地。

二哥想跑出一个尽量长的距离，这样被抢断的几率就比较低。

希望你帮他决定每一秒究竟该停在原地还是向固定的方向移动。

Input Format

输入文件的第一行包含5个数N, M, x, y和K。N和M描述比赛场地的大小，x和y为二哥的初始位置；

以下N行，每行M个字符，描述场地里的地形。第i 行第j 列的字符若为'.'，则表示该位置是空地；若为'x'，则表示有障碍物。

以下K行，顺序描述K个时间区间，格式为：si ti di(\( 1 \leq i \leq K \) )。表示在时间区间[si,ti]内，二哥必须向di方向移动（或者停在原地）。di为1, 2, 3, 4中的一个，依次表示北、南、西、东（分别对应矩阵中的上、下、左、右）。输入保证区间是连续的，即 s1=1 ; si=T(i-1)+1,\( ( 1 < i \leq K) \) ; tK=T 。

Output Format

输出文件仅有1行，包含一个整数，表示二哥能跑出的最长距离(即格子数)。

说明

样例说明

二哥的移动路线：

二哥在“×”位置上时停留一次，因此总共的移动距离为6。

数据范围

50%的数据中，\( 1 \leq N, M \leq 200，T \leq 200 \)；

100%的数据中，\( 1 \leq N, M \leq 200，K \leq 200，T \leq 40000 \)。

Sample Input

4 5 4 1 3 
..xx. 
..... 
...x. 
..... 
1 3 4 
4 5 1 
6 7 2

Sample Output

FineArtz's solution

/* 足球游戏 */
#include <iostream>
#include <cstring>
using namespace std;

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

pair<int, int> q[205], tmp;
int f[205][205];
bool a[205][205];
int n, m, k, x, y, ans = 0;

void dp(int x, int y, int l, int d) {
    int front = 0, rear = 0;
    int i = 0;
    while (x >= 1 && x <= n && y >= 1 && y <= m){
        if (!a[x][y]){
            front = 0;
            rear = 0;
        }
        else{
            tmp = make_pair(f[x][y], i);
            while (front < rear && q[rear - 1].first + i - q[rear - 1].second <= tmp.first)
                --rear;
            q[rear++] = tmp;
            while (front < rear && i - q[front].second > l)
                ++front;
            f[x][y] = q[front].first + i - q[front].second;
            ans = max(ans, f[x][y]);
        }
        ++i;
        x += dx[d];
        y += dy[d];
    }
}

int main(){
    cin >> n >> m >> x >> y >> k;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            char ch;
            cin >> ch;
            if (ch == '.')
                a[i][j] = true;
            else
                a[i][j] = false;
        }
    }
    memset(f, 0x80, sizeof(f));
    f[x][y] = 0;
    while (k--){
        int s, e, d, l;
        cin >> s >> e >> d;
        l = e - s + 1;
        if (d == 1)
            for (int j = 1; j <= m; ++j)
                dp(n, j, l, 0);
        else if (d == 2)
            for (int j = 1; j <= m; ++j)
                dp(1, j, l, 1);
        else if (d == 3)
            for (int i = 1; i <= n; ++i)
                dp(i, m, l, 2);
        else
            for (int i = 1; i <= n; ++i)
                dp(i, 1, l, 3);
    }
    cout << ans << endl;;
    return 0;
}