思路：

1. dp[k][x][y] 表示处理到第 k 个时间区间时，最终点落在 x, y 坐标上，移动的最大距离。

3. dp[k][x][y] = max(dp[k-1][x1][y1] + delta); 由于 delta 是相对偏移量，所以对于 x/y 所在的维度可以用单调队列优化。

4. 由于第 k - 1 次之后，无法确定第 k 步的起始位置，所以要采取枚举的办法，所以最终的时间复杂度为 O(N*M*K)

5. 初始状态为 dp[0][x][y] = 0, 其他赋值为 -INFS，这样才能保证枚举的过程中，最终结果是在以 (x, y) 为起始点出发的。

 

#include <iostream>

#include <cstdio>

#include <algorithm>

using

namespace

std;

 

const

int

MAXN = 210;

const

int

INFS = 0x3fffffff;

 

int

dx[5] = {-1, 1, 0, 0};

int

dy[5] = {0, 0, -1, 1};

 

char

grid[MAXN][MAXN];

int

t1, t2, dp[2][MAXN][MAXN], deq[MAXN], pos[MAXN];

 

void

solvedp(

int

x,

int

y,

int

width,

int

size,

int

d)

{

    

int

s = 0, e = -1;

    

for

(

int

i = 1; i <= width; ++i)

    

{

        

if

(grid[x][y] ==

'.'

)

        

{

            

int

val = dp[t1][x][y] - i;

            

while

(s <= e && deq[e] < val)

                

--e;

 

            

deq[++e] = val, pos[e] = i;

            

while

(i - pos[s] > size)

                

++s;

 

            

dp[t2][x][y] = deq[s] + i;

        

}

        

else

        

{

            

s = 0, e = -1;

            

dp[t2][x][y] = -INFS;

        

}

        

x += dx[d], y += dy[d];

    

}

}

 

int

main()

{

    

int

N, M, x, y, K;

    

while

(

scanf

(

"%d %d %d %d %d"

, &N, &M, &x, &y, &K) != EOF)

    

{

        

for

(

int

i = 1; i <= N; ++i)

            

scanf

(

"%s"

, &grid[i][1]);

 

        

for

(

int

i = 1; i <= N; ++i)

            

for

(

int

j = 1; j <= M; ++j)

                

dp[0][i][j] = -INFS;

        

dp[0][x][y] = 0;

 

        

t1 = 1, t2 = 0;

        

for

(

int

i = 0; i < K; ++i)

        

{

            

int

si, ti, di;

            

scanf

(

"%d %d %d"

, &si, &ti, &di);

 

            

t1 ^= 1, t2 ^= 1;

             

            

if

(di == 1)

            

{

                

for

(

int

j = 1; j <= M; ++j)

                    

solvedp(N, j, N, ti - si + 1, di - 1);

            

}

            

else

if

(di == 2)

            

{

                

for

(

int

j = 1; j <= M; ++j)

                    

solvedp(1, j, N, ti - si + 1, di - 1);

            

}

            

else

if

(di == 3)

            

{

                

for

(

int

j = 1; j <= N; ++j)

                    

solvedp(j, M, M, ti - si + 1, di - 1);

            

}

            

else

if

(di == 4)

            

{

                

for

(

int

j = 1; j <= N; ++j)

                    

solvedp(j, 1, M, ti - si + 1, di - 1);

            

}

        

}

 

        

int

ans = 0;

        

for

(

int

i = 1; i <= N; ++i)

            

for

(

int

j = 1; j <= M; ++j)

                

ans = max(ans, dp[t2][i][j]);

 

        

printf

(

"%d\n"

, ans);

    

}

    

return

0;

}