bzoj1193

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<queue>

 using namespace std ;

 int d [  ] [  ] ;

 int ha ( const int x , const int y ) {

     if ( x ==  && y ==  ) return  ;

     typedef pair < int , int > p ;

     queue < p > q ;

     for ( int i =  ; i <  ; ++ i )

          for ( int y =  ; y <  ; ++ y ) d [ i ] [ y ] = -  ;

     d [  ] [  ] =  ;

     q . push ( make_pair (  ,  ) ) ;

     while ( q . size () ) {

         const p o = q . front () ; q . pop () ;

         if ( abs ( o . first -  ) >  || abs ( o . second -  ) >  ) continue ;

         const int x_ [] = {  ,  ,  ,  , - , - , - , - } ;

         const int y_ [] = {  , - ,  , - ,  , - ,  , - } ;

         for ( int i =  ; i <  ; ++ i ) {

             const int nx = o . first + x_ [ i ] ;

             const int ny = o . second + y_ [ i ] ;

             if ( nx == x +  && ny == y +  ) return d [ o . first ] [ o . second ] +  ;

             if ( d [ nx ] [ ny ] == -  ) {

                 d [ nx ] [ ny ] = d [ o . first ] [ o . second ] +  ;

                 q . push ( make_pair ( nx , ny ) ) ;

             }

         }

     }

     exit ( - ) ;

 }

 int xp , yp , xs , ys ;

 int x , y ;

 int step_cnt =  ;

 int main () {

     scanf ( "%d%d%d%d" , & xp , & yp , & xs , & ys ) ;

     x = abs ( xp - xs ) ; y = abs ( yp - ys ) ;

     while ( abs ( x ) + abs ( y ) >=  ) {

         if ( abs ( x ) >= abs ( y ) ) {

             const int step = abs ( x /  ) ;

             x -= ( ( x >  ) ? step : - step ) *  ;

             y -= ( y >  ) ? step : - step ;

             step_cnt += abs ( step ) ;

         } else {

             const int step = abs ( y /  ) ;

             x -= ( x >  ) ? step : - step ;

             y -= ( y >  ? step : - step ) *  ;

             step_cnt += abs ( step ) ;

         }

     }

     printf ( "%d\n" , step_cnt + ha ( abs ( x ) , abs ( y ) ) ) ;

     return  ;

 }

贪心+bfs