大概就是设$dp[i][x][y]$表示在第$i$个时间段，在$(x,y)$时的最大滑动距离

然后转移是$dp[i][x][y]=max(dp[i-1][x][y],dp[i][x'][y']+dis(x,y,x',y'))$

然后用单调队列进行优化，遇到障碍清除整个单调队列

1 //minamoto 2 #include
     
       3 #include
      
        4 const int N=205; 5 template
       
        inline bool cmax(T&a,const T&b){
   return a
        
         =1&&x<=n&&y>=1&&y<=m;++i,x+=dx[d],y+=dy[d])16     if(mp[x][y]=='x') h=1,t=0;17     else{18         while(h<=t&&q[t].dp+i-q[t].pos
         
          len) ++h;21         dp[x][y]=q[h].dp+i-q[h].pos;22         cmax(ans,dp[x][y]);23     }24 }25 int main(){26 //    freopen("testdata.in","r",stdin);27     scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&k);28     for(int i=1;i<=n;++i) scanf("%s",mp[i]+1);29     memset(dp,0xef,sizeof(dp));30     dp[sx][sy]=0;31     while(k--){32         int s,t,d;scanf("%d%d%d",&s,&t,&d);33         int len=t-s+1;34         switch(d){35             case 1:for(int i=1;i<=m;++i) solve(n,i,len,d);break;36             case 2:for(int i=1;i<=m;++i) solve(1,i,len,d);break;37             case 3:for(int i=1;i<=n;++i) solve(i,m,len,d);break;38             case 4:for(int i=1;i<=n;++i) solve(i,1,len,d);break;39         }40     }41     printf("%d\n",ans);42     return 0;43 }