fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define inf (1LL<<62)
  7. #define ff first
  8. #define ss second
  9.  
  10. int n, m, l, t;
  11. char s[3005][3005];
  12. deque<pair<ll,int>>q[3005];
  13. ll dp[3005][3005];
  14.  
  15. int main()
  16. {
  17.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  18.  
  19.     cin>>n>>m>>l>>t;
  20.  
  21.     for(int i=0; i<n; i++){
  22.         cin>>s[i];
  23.     }
  24.  
  25.     for(int i=0; i<n; i++){
  26.         for(int j=0; j<m; j++){
  27.             dp[i][j]=inf;
  28.         }
  29.     }
  30.  
  31.     dp[0][0]=0;
  32.     q[m].push_back({0,0});//horizontal queue
  33.     q[0].push_back({0,0});//0 -> m-1 vertical queue
  34.  
  35.     for(int i=0; i<n; i++){
  36.         for(int j=(i==0)?1:0; j<m; j++){
  37.             if(s[i][j]=='#'){
  38.                 while(!q[m].empty()) q[m].pop_back();
  39.                 while(!q[j].empty()) q[j].pop_back();
  40.                 continue;
  41.             }
  42.  
  43.             while(!q[m].empty() && q[m].front().ss<j-l){
  44.                 q[m].pop_front();
  45.             }
  46.             while(!q[j].empty() && q[j].front().ss<i-l){
  47.                 q[j].pop_front();
  48.             }
  49.  
  50.             int x=-1, y=-1;
  51.             if(!q[m].empty()) y=q[m].front().ss;
  52.             if(!q[j].empty()) x=q[j].front().ss;
  53.  
  54.             if(y!=-1) dp[i][j]=min(dp[i][j],dp[i][y]+t+(j-y));
  55.             if(x!=-1) dp[i][j]=min(dp[i][j],dp[x][j]+t+(i-x));
  56.  
  57.             if(dp[i][j]<inf){
  58.                 while(!q[m].empty() && q[m].back().ff>=dp[i][j]-j) q[m].pop_back();
  59.                 q[m].push_back({dp[i][j]-j,j});
  60.                 while(!q[j].empty() && q[j].back().ff>=dp[i][j]-i) q[j].pop_back();
  61.                 q[j].push_back({dp[i][j]-i,i});
  62.             }
  63.         }
  64.  
  65.         while(!q[m].empty()) q[m].pop_front();
  66.     }
  67.  
  68.     if(dp[n-1][m-1]==inf) cout<<-1<<'\n';
  69.     else cout<<dp[n-1][m-1]<<'\n';
  70.  
  71.     return 0;
  72. }
Success #stdin #stdout 0.01s 7456KB
comments (?)
stdin
copy 
3 4
2 2
....
##..
#...
stdout
copy 
11
https://ideone.com/wO7IUJ
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!