给你k次移动
每次移动给你一个时间段 a,b和方向dir
地图上有障碍物
为了不撞上障碍物你可以施法让箱子停下来
问箱子可以走的最长路
（（以下是洛谷的题解））
/*首先考虑对于时间t来dp： f[t][i][j]表示在第t时刻在第i行第j列所能获得的最长距离。
转移方程：f[t][i][j]=max(f[t-1][i][j],f[t][i*][j*]+1)(i*,j*为上一个合理的位置) 这样时间复杂度为O(TNM)，可以过50%,但对于100%TLE且MLE。
所以必须优化，首先把时间t换成区间k， 令f[k][i][j]表示在第k段滑行区间中在位置i，
j所能获得最长距离 注意到在第k段时间内只能向某个方向最多走x步（x为区间长度），
得到转移方程 f[k][i][j]=max(f[k-1][i][j],f[k][i*][j*]+dis(i,j,i*,j*))(i*,j*为上一个合理的位置) 这个做法的时间复杂度是O(kn^3)，会超时，
需要进一步优化 用单调队列优化掉内层的一个n，就可以做到O(kn^2)，可以AC，
本代码中还使用了滚动数组优化 用单调递减队列求最大值时，遇到障碍清空整个队列即可，另外队列比较时需要加上偏移量dis*/
1 #include<bits/stdc++.h> 2 #define mp make_pair 3 #define pb push_back 4 #define first fi 5 #define second se 6 #define pw(x) (1ll << (x)) 7 #define sz(x) ((int)(x).size()) 8 #define all(x) (x).begin(),(x).end() 9 #define rep(i,l,r) for(int i=(l);i<(r);i++) 10 #define per(i,r,l) for(int i=(r);i>=(l);i--) 11 #define FOR(i,l,r) for(int i=(l);i<=(r);i++) 12 #define eps 1e-9 13 #define PIE acos(-1) 14 #define cl(a,b) memset(a,b,sizeof(a)) 15 #define fastio ios::sync_with_stdio(false);cin.tie(0); 16 #define lson l , mid , ls 17 #define rson mid + 1 , r , rs 18 #define ls (rt<<1) 19 #define rs (ls|1) 20 #define INF 0x3f3f3f3f 21 #define LINF 0x3f3f3f3f3f3f3f3f 22 #define freopen freopen("in.txt","r",stdin); 23 #define cfin ifstream cin("in.txt"); 24 #define lowbit(x) (x&(-x)) 25 #define sqr(a) a*a 26 #define ll long long 27 #define ull unsigned long long 28 #define vi vector<int> 29 #define pii pair<int, int> 30 #define dd(x) cout << #x << " = " << (x) << ", " 31 #define de(x) cout << #x << " = " << (x) << " " 32 #define endl " " 33 using namespace std; 34 //********************************** 35 const int maxn=207; 36 const int dx[]={0,-1,1,0,0},dy[]={0,0,0,-1,1}; 37 int n,m,X,Y,k; 38 char pic[maxn][maxn]; 39 int dp[maxn][maxn]; 40 int ans; 41 struct node{ 42 int id,v; 43 }que[maxn]; 44 //********************************** 45 inline bool in(int x,int y) 46 { 47 return x>=1&&x<=n&&y>=1&&y<=m; 48 } 49 void solve(int x,int y,int len,int dir) 50 { 51 int head=1,tail=0; 52 for(int i=0;in(x,y);++i,x+=dx[dir],y+=dy[dir]){ 53 if(pic[x][y]=='x') head=1,tail=0; 54 else { 55 while(head<=tail&&que[tail].v+i-que[tail].id<dp[x][y])tail--; 56 que[++tail]=node{i,dp[x][y]}; 57 if(que[tail].id-que[head].id>len)++head; 58 dp[x][y]=que[head].v+i-que[head].id; 59 ans=max(ans,dp[x][y]); 60 } 61 } 62 } 63 //********************************** 64 int main() 65 { 66 // freopen; 67 ans=0; 68 scanf("%d %d %d %d %d",&n,&m,&X,&Y,&k); 69 cl(dp,-INF);dp[X][Y]=0; 70 FOR(i,1,n)scanf("%s",pic[i]+1); 71 // FOR(i,1,n)printf("%s ",pic[i]+1); 72 FOR(i,1,k){ 73 int a,b,dir; 74 scanf("%d %d %d",&a,&b,&dir); 75 int len=b-a+1; 76 if(dir==1)FOR(i,1,m)solve(n,i,len,1); 77 else if(dir==2)FOR(i,1,m)solve(1,i,len,2); 78 else if(dir==3)FOR(i,1,n)solve(i,m,len,3); 79 else if(dir==4)FOR(i,1,n)solve(i,1,len,4); 80 } 81 // de(dp[4][2]); 82 printf("%d ",ans); 83 return 0; 84 }