結果

問題 No.124 門松列(3)
ユーザー Ysmr_RyYsmr_Ry
提出日時 2015-01-18 16:38:54
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,392 bytes
コンパイル時間 437 ms
コンパイル使用メモリ 52,772 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-04 21:36:16
合計ジャッジ時間 1,756 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 3 ms
4,380 KB
testcase_04 AC 3 ms
4,380 KB
testcase_05 AC 3 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 2 ms
4,384 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 2 ms
4,380 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 2 ms
4,380 KB
testcase_28 AC 3 ms
4,376 KB
testcase_29 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// yukicoder 124 (http://yukicoder.me/problems/222)
#include<cstdio>
#include<algorithm>
#include<limits>
#include<queue>
#define rep(i,a) for(int i=0;i<(a);++i)

typedef std::pair<int, int> P;

const int MAX_H = 100, MAX_W = 100, dr[5] = { 0, -1, 0, 1, 0 }, INF = std::numeric_limits<int>::max()>>2;

struct St
{
	P p;
	int prv, dist;

	St( const P &p, int prv, int dist )
	:	p(p), prv(prv), dist(dist)
	{}
};

int W, H;
int M[MAX_H][MAX_W], dist[9][MAX_H][MAX_W];

bool isKS( int a, int b, int c )
{
	int ar[3] = {a,b,c};
	std::sort( ar, ar+3 );

	return a!=b && b!=c && c!=a && ar[1]!=b;
}

int main()
{
	scanf( "%d%d", &W, &H );
	rep( i, H ) rep( j, W )
		scanf( "%d", &M[i][j] ), --M[i][j];

	rep( i, 9 ) rep( j, H ) rep( k, W )
		dist[i][j][k] = INF;

	dist[0][0][0] = 0;
	std::queue<St> que;
	que.push( St( P(0,0), 0, 0 ) );
	while( !que.empty() )
	{
		St st = que.front(); que.pop();
		int i = st.p.first, j = st.p.second;

		rep( d, 4 )
		{
			int ni = i+dr[d], nj = j+dr[d+1];
		
			if( dist[M[i][j]][ni][nj] != INF )
				continue;
			if( (i||j) && !isKS( M[ni][nj], M[i][j], st.prv ) )
				continue;

			if( ni >= 0 && ni < H && nj >= 0 && nj < W )
			{
				que.push( St( P(ni,nj), M[i][j], st.dist+1 ) );
				dist[M[i][j]][ni][nj] = st.dist+1;
			}
		}
	}

	int ans = INF;
	rep( i, 9 )
		ans = std::min( ans, dist[i][H-1][W-1] );

	printf( "%d\n", ans==INF?-1:ans );

	return 0;
}
0