結果

問題 No.124 門松列(3)
コンテスト
ユーザー Ysmr_Ry
提出日時 2015-01-18 16:35:18
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,370 bytes
コンパイル時間 414 ms
コンパイル使用メモリ 51,304 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-22 19:05:23
合計ジャッジ時間 1,396 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18 WA * 8
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:35:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   35 |         scanf( "%d%d", &W, &H );
      |         ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:37:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   37 |                 scanf( "%d", &M[i][j] ), --M[i][j];
      |                 ~~~~~^~~~~~~~~~~~~~~~~~

ソースコード

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 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( st.prv && !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