题目大意：给你一个n*m棋盘(n,m<=200)，有一个人从给定的点s,e出发，有一些坏点不能走，一共给定k段连续的时间(k<=200)，在某一段时间之内它只能向一个给定的方向移动，在某一时刻，它可以移动或者不移动。求碰到坏点之前/总时间结束时，最长移动的距离。
朴素DP的方法是： 表示在时间点t时，在位置(i,j)时已经走过的最长距离，i' j'表示这一步移动前的位置
得到方程
空间时间都会炸
那么重新定义 表示在第k个时间段，在位置(i,j)时已经走过的最长距离
那么显然，注意要根据移动的方向决定枚举的顺序
由于dis在同一行/列具有单调性，用队列随便优化一下就行了，如果dis大于t[i]-s[i]就删除队首，如果碰到障碍就清队列
1 #include2 #include 3 #include 4 #define N 205 5 using namespace std; 6 7 int n,m,sx,sy,K,now,pst; 8 int mp[N][N],st[N],ed[N],dir[N],que[N]; 9 int xx[]={ 0,-1,1,0,0},yy[]={ 0,0,0,-1,1}; 10 char str[N][N]; 11 int f[2][N][N]; 12 void upd1(int k) 13 { 14 int hd,tl; 15 for(int j=1;j<=m;j++) 16 { 17 hd=1,tl=0; 18 for(int i=n;i>=1;i--) 19 { 20 if(mp[i][j]) {hd=1,tl=0;continue;} 21 while(hd<=tl&&f[pst][que[tl]][j]+que[tl]-i<=f[pst][i][j]) 22 tl--; 23 que[++tl]=i; 24 while(hd<=tl&&que[hd]-i>ed[k]-st[k]+1) 25 hd++; 26 f[now][i][j]=f[pst][que[hd]][j]+que[hd]-i; 27 } 28 } 29 } 30 void upd2(int k) 31 { 32 int hd,tl; 33 for(int j=1;j<=m;j++) 34 { 35 hd=1,tl=0; 36 for(int i=1;i<=n;i++) 37 { 38 if(mp[i][j]) {hd=1,tl=0;continue;} 39 while(hd<=tl&&f[pst][que[tl]][j]+i-que[tl]<=f[pst][i][j]) 40 tl--; 41 que[++tl]=i; 42 while(hd<=tl&&i-que[hd]>ed[k]-st[k]+1) 43 hd++; 44 f[now][i][j]=f[pst][que[hd]][j]+i-que[hd]; 45 } 46 } 47 } 48 void upd3(int k) 49 { 50 int hd,tl; 51 for(int i=1;i<=n;i++) 52 { 53 hd=1,tl=0; 54 for(int j=m;j>=1;j--) 55 { 56 if(mp[i][j]) {hd=1,tl=0;continue;} 57 while(hd<=tl&&f[pst][i][que[tl]]+que[tl]-j<=f[pst][i][j]) 58 tl--; 59 que[++tl]=j; 60 while(hd<=tl&&que[hd]-j>ed[k]-st[k]+1) 61 hd++; 62 f[now][i][j]=f[pst][i][que[hd]]+que[hd]-j; 63 } 64 } 65 } 66 void upd4(int k) 67 { 68 int hd,tl; 69 for(int i=1;i<=n;i++) 70 { 71 hd=1,tl=0; 72 for(int j=1;j<=m;j++) 73 { 74 if(mp[i][j]) {hd=1,tl=0;continue;} 75 while(hd<=tl&&f[pst][i][que[tl]]+j-que[tl]<=f[pst][i][j]) 76 tl--; 77 que[++tl]=j; 78 while(hd<=tl&&j-que[hd]>ed[k]-st[k]+1) 79 hd++; 80 f[now][i][j]=f[pst][i][que[hd]]+j-que[hd]; 81 } 82 } 83 } 84 85 int main() 86 { 87 scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&K); 88 for(int i=1;i<=n;i++){ 89 scanf("%s",str[i]+1); 90 for(int j=1;j<=m;j++) 91 if(str[i][j]=='x') 92 mp[i][j]=1; 93 } 94 for(int i=1;i<=K;i++) 95 scanf("%d%d%d",&st[i],&ed[i],&dir[i]); 96 memset(f,-0x3f,sizeof(f)); 97 f[0][sx][sy]=0; 98 now=1,pst=0; 99 for(int k=1;k<=K;k++)100 {101 if(dir[k]==1) upd1(k);102 if(dir[k]==2) upd2(k);103 if(dir[k]==3) upd3(k);104 if(dir[k]==4) upd4(k);105 swap(now,pst);106 }107 int ans=0;108 for(int i=1;i<=n;i++)109 for(int j=1;j<=m;j++)110 ans=max(f[pst][i][j],ans);111 printf("%d\n",ans);112 return 0;113 }