SRM456 Div1 Easy

250
山登り

view plainprint?

1. class SilverDistance {  
2. public:  
3.   int minSteps(int sx, int sy, int gx, int gy) {  
4.     int    cnt = 0;  
5.     while( sx != gx || sy != gy ){  
6.       double dist[5];  
7.       int nx[5], ny[5];  
8.       const int dx[] = {-1, -1, 0, +1, +1};  
9.       const int dy[] = {-1, +1, 1, -1, +1};  
10.       for(int d=0; d<5; ++d){  
11.         nx[d] = sx + dx[d];  
12.         ny[d] = sy + dy[d];  
13.         double x = nx[d] - gx;  
14.         double y = ny[d] - gy;  
15.         dist[d] = sqrt( x * x + y * y );  
16.       }  
17.       int mn = min_element( dist, dist + 5 ) - dist;  
18.       sx = nx[mn];  
19.       sy = ny[mn];  
20.       ++cnt;  
21.     }  
22.   
23.     return cnt;  
24.   }  
25.   
26. };  

class SilverDistance {
public:
  int minSteps(int sx, int sy, int gx, int gy) {
    int    cnt = 0;
    while( sx != gx || sy != gy ){
      double dist[5];
      int nx[5], ny[5];
      const int dx[] = {-1, -1, 0, +1, +1};
      const int dy[] = {-1, +1, 1, -1, +1};
      for(int d=0; d<5; ++d){
        nx[d] = sx + dx[d];
        ny[d] = sy + dy[d];
        double x = nx[d] - gx;
        double y = ny[d] - gy;
        dist[d] = sqrt( x * x + y * y );
      }
      int mn = min_element( dist, dist + 5 ) - dist;
      sx = nx[mn];
      sy = ny[mn];
      ++cnt;
    }

    return cnt;
  }

};