Skip to content

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

6

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;
}