KOI 물통 첨삭1

koi_bucket_edit1.cpp

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <utility>

using namespace std;
queue< pair < int , int > > q;
int memo[100001][4] , A , B;

void push( int x , int y , int t )
{
	if( x == A && memo[y][0] == 2e9 )
	{
		memo[y][0] = t;
		q.push( make_pair(x,y) );
		return;
	}
	if( x == 0 && memo[y][1] == 2e9 )
	{
		memo[y][1] = t;
		q.push( make_pair(x,y) );
		return;
	}
	if( y == B && memo[x][2] == 2e9 )
	{
		memo[x][2] = t;
		q.push( make_pair(x,y) );
		return;
	}
	if( y == 0 && memo[x][3] == 2e9 )
	{
		memo[x][3] = t;
		q.push( make_pair(x,y) );
		return;
	}
}

int main() {
	int a , b , m1 , m2;
	pair< int , int > p;
	scanf("%d %d %d %d", &A , &B , &a , &b );
	for( int i = 0 ; i <= B ; i++ )
		for( int j = 0 ; j < 4 ; j++ )
			memo[i][j] = 2e9;
	
	if( a == A )
	{
		m1 = b;
		m2 = 0;
	}
	else if( a == 0 )
	{
		m1 = b;
		m2 = 1;
	}
	else if( b == B )
	{
		m1 = a;
		m2 = 2;
	}
	else if( b == 0 )
	{
		m1 = a;
		m2 = 3;
	}
	else
	{
		printf("-1");
		return 0;
	}
	
	push( 0 , 0 , 0 );
	
	while( q.empty() == 0 )
	{
		int x , y , t;
		p = q.front();
		q.pop();
		x = p.first;
		y = p.second;
		
		if( x == A ) t = memo[y][0];
		else if( x == 0 ) t = memo[y][1];
		else if( y == B ) t = memo[x][2];
		else t = memo[x][3];
		
		//printf("%d %d %d\n", x , y , t );

		if( y-(A-x) >= 0 ) push( A , y-(A-x) , t+1 ); // 물통B->물통A로 옮김(옮겼을 때 물통A가 꽉 차는 경우)
		if( x-(B-y) >= 0 ) push( x-(B-y) , B , t+1 ); // 물통A->물통B로 옮김(옮겼을 때 물통B가 꽉 차는 경우)
		if( x+y <= A ) push( x+y , 0 , t+1 ); // 물통B->물통A로 옮김(옮겼을 때 물통A가 꽉 차지 않는 경우)
		if( x+y <= B ) push( 0 , x+y , t+1 ); // 물통A->물통B로 옮김(옮겼을 때 물통B가 꽉 차지 않는 경우)
		push( A , y , t+1 );
		push( 0 , y , t+1 );
		push( x , B , t+1 );
		push( x , 0 , t+1 );
	}
	printf("%d", memo[m1][m2] != 2e9 ? memo[m1][m2] : -1); // memo가 2e9일 경우는(불가능) 2e9가 아니라 -1을 출력해야 함
	return 0;
}