#include #include #include using namespace std; struct Position { int x; int y; }; struct InnerData { Position pos; int cost; }; typedef queue InnerDataQueue; typedef vector PositionVector; Position MakePosition ( int x , int y ); int main ( void ) { Position target; Position wall; scanf ( "%d %d" , &target.x , &target.y ); scanf ( "%d %d" , &wall.x , &wall.y ); InnerData idst; idst.pos.x = 0; idst.pos.y = 0; idst.cost = 0; PositionVector history; InnerDataQueue idq; InnerData id , idnext; idq.push ( idst ); int AlreadyScanned; while ( idq.empty() == false ) { id = idq.front (); idq.pop (); if ( ( id.pos.x == wall.x ) && ( id.pos.y == wall.y ) ) continue; if ( ( id.pos.x == target.x ) && ( id.pos.y == target.y ) ) { printf ( "%d\n" , id.cost ); break; } AlreadyScanned = 0; if ( history.empty () == false ) { for ( unsigned int i = history.size () - 1; i >= 1; i-- ) { if ( ( history [ i ].x == id.pos.x ) && ( history [ i ].y == id.pos.y ) ) { AlreadyScanned = 1; break; } } if ( ( history [ 0 ].x == id.pos.x ) && ( history [ 0 ].y == id.pos.y ) ) { AlreadyScanned = 1; } } if ( AlreadyScanned == 1 )continue; history.push_back ( id.pos ); idnext.cost = id.cost + 1; //左上 idnext.pos = MakePosition ( id.pos.x - 1 , id.pos.y - 1 ); idq.push ( idnext ); //上 idnext.pos = MakePosition ( id.pos.x , id.pos.y - 1 ); idq.push ( idnext ); //右上 idnext.pos = MakePosition ( id.pos.x + 1 , id.pos.y - 1 ); idq.push ( idnext ); //左 idnext.pos = MakePosition ( id.pos.x - 1 , id.pos.y ); idq.push ( idnext ); //右 idnext.pos = MakePosition ( id.pos.x + 1 , id.pos.y ); idq.push ( idnext ); //左下 idnext.pos = MakePosition ( id.pos.x - 1 , id.pos.y + 1 ); idq.push ( idnext ); //下 idnext.pos = MakePosition ( id.pos.x , id.pos.y + 1 ); idq.push ( idnext ); //右下 idnext.pos = MakePosition ( id.pos.x + 1 , id.pos.y + 1 ); idq.push ( idnext ); } return 0; } Position MakePosition ( int x , int y ) { Position pos; pos.x = x; pos.y = y; return pos; }