fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. //#define mp make_pair
  3. #define pb push_back
  4. #define vi vector<int>
  5. #define pii pair<int,int>
  6. #define vii vector<pii>
  7. #define rep(i,n) for(int i = 0; i < n; i++)
  8. #define rp(i,a,n) for(int i=a;i<=int(n);i++)
  9. #define IT(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
  10. #define all(x) (x).begin(), (x).end()
  11. #define ll long long
  12. #define oo INT_MAX
  13. #define fill(a,b) memset(a,b,sizeof a)
  14. #define F first
  15. #define S second
  16. #define mod 1000000007
  17. using namespace std;
  18. int dr[8] = {1,1,0,-1,-1,-1, 0, 1};
  19. int dc[8] = {0,1,1, 1, 0,-1,-1,-1};
  20. int dh[4] = {0, 1, 0, -1};
  21. int dv[4] = {-1, 0, 1, 0};
  22.  
  23. int n,m,a,b;
  24. char s[550][550],mp[550][550];
  25. int vis[550][550];
  26. ll ans[550][550];
  27.  
  28. void dfs(int x,int y,char c)
  29. {
  30.     if(vis[x][y]||s[x][y]!='.') return ;
  31.     vis[x][y]=1;
  32.     mp[x][y]=c;
  33.     rep(i,4) dfs(x+dh[i],y+dv[i],c=='T'?'W':'T');
  34. }
  35. void dfs2(int x,int y,ll cnt)
  36. {
  37.     if(vis[x][y]||s[x][y]!='.') return ;
  38.     vis[x][y]=1;
  39.     ans[x][y]=min(ans[x][y],cnt);
  40.     if(mp[x][y]=='T') cnt+=a;else cnt+=b;
  41.     rep(i,4) dfs2(x+dh[i],y+dv[i],cnt);
  42. }
  43. int main()
  44. {
  45.     cin >> n >> m >> a >> b;
  46.     swap(n,m);
  47.     rep(i,n+5) rep(j,m+5)  s[i][j]=mp[i][j]='#' ;
  48.     for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> s[i][j];
  49.     dfs(1,1,'T');
  50.     if(!vis[n][m]) { cout << "IMPOSSIBLE\n"; return 0; }
  51.     for(int i=0;i<=n+5;i++) for(int j=0;j<=m+5;j++) vis[i][j]=0,ans[i][j]=1000000000;
  52.     dfs2(1,1,0);
  53.     cout << ans[n][m] << "\n";
  54.  
  55.  
  56. }
  57.  
Success #stdin #stdout 0s 6868KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
IMPOSSIBLE
https://ideone.com/PciZ3S
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
public

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!