Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 5th, 2012  |  syntax: C++  |  size: 4.25 KB  |  hits: 18  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <sstream>
  4. #include <string>
  5. #include <vector>
  6. #include <cstdio>
  7. #include <cmath>
  8. #include <cstring>
  9. #include <map>
  10. #include <set>
  11. #include <ctime>
  12. #include <queue>
  13.  
  14. using namespace std;
  15.  
  16. typedef long long LL;
  17. typedef unsigned long long ULL;
  18. #define sz(X) ((int)(X).size())
  19. #define FOREACH(i,c) for(__typeof(c.begin()) i=(c.begin());i!=(c).end();++i)
  20. #define IN(_lower,_variable,_higher) (((_lower)<=(_variable)) && ((_variable)<=(_higher)))
  21. #define REP(i,n) for(int i=0;i<(n);++i)
  22. #define FORU(v,p,k) for(int v=p;v<k;++v)
  23. #define FORD(v,p,k) for(int v=(p)-1;v>=k;--v)
  24. #define FORLLU(v,p,k) for(LL v=p;v<k;++v)
  25. #define FORLLD(v,p,k) for(LL v=(p)-1;v>=k;--v)
  26. template<class T> vector<T> tokenize_to(const string &str) { vector<T> r; T x; istringstream is(str); while (is >> x) r.push_back(x); return r; }
  27. #define junik(X) {sort( (X).begin(), (X).end() ); (X).erase( unique( (X).begin(), (X).end() ), (X).end() ); }
  28. #define min(x,y) (((x)<(y))?(x):(y))
  29. #define max(x,y) (((x)>(y))?(x):(y))
  30.  
  31.  
  32. #define MAXV 1e20
  33.  
  34.  
  35. double best [100][100];
  36. int c[100][100];
  37. int  f[100][100];
  38.  
  39. class state{
  40.   public:
  41.   int x, y;
  42.   double t;
  43.   state(int _x, int _y, double _t){
  44.     x=_x; y=_y; t=_t;
  45.   }
  46.   const bool operator<(const state &drugi) const {    
  47.     if (x<drugi.x) return true;
  48.     if (x>drugi.x) return false;
  49.     if (y<drugi.y) return true;
  50.     if (y>drugi.y) return false;
  51.     if (t<drugi.t) return true;
  52.     if (t>drugi.t) return false;  
  53.     return true;
  54.   }
  55.   const bool operator==(const state &drugi) const {    
  56.     return (x==drugi.x && y==drugi.y && t == drugi.t);
  57.   }
  58.  
  59. };
  60.  
  61. queue<state> q;
  62.   vector<state> start;
  63.   int h, m, n;
  64.  
  65. int outOfGrid(int x, int y) {
  66.   return (x<0 || y<0 || x>=n || y>=m);
  67.  
  68. }
  69.  
  70. bool tryToGo(int c1, int f1, int c2, int f2, int h){
  71.   if (h+50>c2) return false;
  72.   if (f1+50>c2) return false;
  73.   if (f2+50>c2) return false;
  74.   if (f2+50>c1) return false;
  75.   return true;
  76. }  
  77.  
  78. void updateStart(state current) {
  79.   for (int i=-1;i<2;i+=2)
  80.     for (int j=-1;j<2;j+=2) {
  81.       if (!outOfGrid(current.x+i, current.y+j) && tryToGo(c[current.x][current.y], f[current.x][current.y], c[current.x+i][current.y+j], f[current.x+i][current.y+j],h ) ) {
  82.         start.push_back(state(current.x+i, current.y+j, 0));
  83.       }
  84.     }
  85. }
  86.  
  87. double getF(int x, int y, double t) {
  88.   return min(f[x][y], h-t*0.1);
  89. }
  90.  
  91. double getT(int x, int y, double goalF) {
  92.   if (f[x][y]>goalF) return -1;
  93.   return (h-goalF)*10;
  94. }
  95.  
  96. double cost(state current, int xNew, int yNew) {
  97.   int c1 = c[current.x][current.y];
  98.   int c2 = c[xNew][yNew];
  99.   int f1Min=c2-50;
  100.   int f2Min=c1-50;
  101.  
  102.   double t1 = getT(current.x, current.y, f1Min);
  103.   double t2 = getT(xNew, yNew, f2Min);
  104.   if (t1 == -1 || t2 == -1) return -1;
  105.   t1 = max (t1, t2);
  106.   double ret=0;
  107.   if (t1>=current.t) ret = 1;
  108.   if (getF(current.x, current.y, t1) - f[current.x][current.y]<20) ret+=10;
  109.  
  110.   return ret;
  111. }
  112.  
  113. double solve() {
  114.   double ret=0;
  115.   scanf("%d %d %d", &h, &n, &m);
  116.   for (int i=0;i<n;i++)
  117.     for(int j=0;j<m;j++)
  118.       scanf("%d ", &c[i][j]);
  119.   for (int i=0;i<n;i++)
  120.     for(int j=0;j<m;j++)
  121.       scanf("%d ", &f[i][j]);
  122.   for (int i=0;i<n;i++)
  123.     for(int j=0;j<m;j++)
  124.       best[i][j]=MAXV;
  125.      
  126.  
  127.   start.clear();
  128.   start.push_back(state(0,0,0));
  129.   best[0][0]=0;
  130.   int nTemp=0;
  131.   do {
  132.     nTemp = sz(start);
  133.     FOREACH(x, start) {
  134.       updateStart(*x);
  135.     }
  136.     junik(start);
  137.   } while  (sz(start)!=nTemp);
  138.  
  139.   while (sz(q)>0) {
  140.     state current=q.front();
  141.     q.pop();
  142.     for (int i=-1;i<2;i+=2)
  143.       for (int j=-1;j<2;j+=2) {
  144.         if (!outOfGrid(current.x+i, current.y+j)) {
  145.           double c = cost(current, current.x+i, current.y+j);
  146.           if (c==-1) continue;
  147.           if (c+current.t<best[current.x+i][current.y+j]) {
  148.             q.push(state(current.x+i, current.y+j, current.t+c));
  149.             best[current.x+i][current.y+j]=c+current.t;
  150.           }
  151.         }
  152.       }
  153.     }
  154.   ret = best[n-1][m-1];
  155.   return ret;
  156. }
  157.  
  158. int main() {
  159.  
  160.   int _n=0;
  161.   scanf("%d ", &_n);
  162.   vector<double> sols;
  163.  
  164.   for (int i=0;i<2;i++) {
  165.     sols.push_back(solve());
  166.   }
  167.   for (int i=0;i<sz(sols);i++) {
  168.     printf("Case #%d: %0.6lf\n", i+1, sols[i]);
  169.   }
  170.  
  171.   return 0;
  172.  
  173. }
create a new version of this paste RAW Paste Data