torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #175, B : Find Marble

概要

1 〜 N に番号付けされた N 個の箱が一列に並んでいる。
一回の操作では、i 番目の箱を p_i に移動させる。
s 番目の箱に玉を入れ、玉を場所 t に移動させるのに必要な操作回数を求めよ。
不可能な場合は -1 を印字せよ。

解法

移動をシミュレーションして回数を数えます。
t に到達する前に一度通った場所に到達する場合、ループしてしまうので不可能です。

コード

typedef vector<int> VI;

#define FOR( v, c ) for ( auto &v : c )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

int solve( int s, int t, const VI &ps )
{
	int cur = s, res = 0;
	set<int> visited;

	while ( cur != t )
	{
		if ( EXIST( visited, cur ) )
		{
			return -1;
		}

		visited.insert( cur );
		cur = ps[ cur ] - 1;
		res++;
	}

	return res;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, s, t;
	cin >> n >> s >> t;

	VI ps( n );
	FOR( p, ps )
	{
		cin >> p;
	}

	cout << solve( s - 1, t - 1, ps ) << endl;

	return 0;
}