結果

問題 No.124 門松列(3)
ユーザー Ysmr_Ry
提出日時 2015-01-18 16:38:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,392 bytes
コンパイル時間 454 ms
コンパイル使用メモリ 51,048 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-22 19:05:26
合計ジャッジ時間 1,376 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0