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

上一篇:6-CSS


下一篇:MySql数据库学习笔记(3)