結果

問題 No.124 門松列(3)
ユーザー koyumeishi
提出日時 2015-01-12 01:14:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 9 ms / 5,000 ms
コード長 2,696 bytes
コンパイル時間 922 ms
コンパイル使用メモリ 87,808 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-22 04:25:13
合計ジャッジ時間 1,895 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
typedef struct{
    int to;
    int cost;
}edge;
//distance from s
//O(E log V)
void dijkstra(vector<vector<edge> > &G, vector<int> &dist, int s){
    //INF as distance
    const int INF = 10000000;
    
    //first : distance from s, second : its vertex
    priority_queue< pair<int,int> , vector<pair<int,int> >, greater< pair<int,int> > > pq;
     
    fill(dist.begin(), dist.end(), INF);
    dist[s] = 0;
    pq.push( make_pair(dist[s], s) );
    while(!pq.empty()){
        pair<int,int> q = pq.top();
        pq.pop();
        int from = q.second;
        if(dist[from] < q.first) continue; // it's not minimum distance
        int n=G[from].size();
        for(int i=0; i<n; i++){
            edge e = G[from][i];
            if(dist[e.to] > dist[from] + e.cost){
                dist[e.to] = dist[from] + e.cost;
                pq.push( make_pair(dist[e.to], e.to) );
            }
        }
    }
}
 
void add_edge(vector<vector<edge> > &G, int from, int to, int cost){
    G[from].push_back( (edge){to, cost} );
    //G[to].push_back( (edge){from, cost} );
}
bool is_kadomatsu_sec(int a, int b, int c){
    if(a==b || b==c || c==a) return false;
    if(b<a && b<c) return true;
    if(b>a && b>c) return true;
    return false;
}
int x[] = {0,1,0,-1};
int y[] = {-1,0,1,0};
int main(){
    int w,h;
    cin >> w >> h;
    vector<vector<int> > v(h, vector<int>(w));
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> v[i][j];
        }
    }
    vector<vector<edge> > G(w*h*4);
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            
            for(int k=0; k<4; k++){
                int xx = j+x[k];
                int yy = i+y[k];
                if(xx<0 || xx>=w) continue;
                if(yy<0 || yy>=h) continue;
                for(int l=0; l<4; l++){
                    if(l==k) continue;
                    int xxx = j+x[l];
                    int yyy = i+y[l];
                    if(xxx<0 || xxx>=w) continue;
                    if(yyy<0 || yyy>=h) continue;
                    if(is_kadomatsu_sec(v[yy][xx], v[i][j], v[yyy][xxx])){
                        add_edge(G, i*w+j + w*h*k, yyy*w+xxx + w*h*((l+2)%4), 1);
                    }
                }
                
            }
            
        }
    }
    const int INF = 10000000;
    int ans = INF;
    vector<int> dist(w*h*4);
    
    for(int i=0; i<4; i++){
        int x1 = 0+x[i];
        int y1 = 0+y[i];
        if(x1<0 || x1>=w) continue;
        if(y1<0 || y1>=h) continue;
        
        for(int j=0; j<4; j++){
            int x2 = x1+x[j];
            int y2 = y1+y[j];
            if(x2<0 || x2>=w) continue;
            if(y2<0 || y2>=h) continue;
            if(x2==0 && y2==0) continue;
            
            
            if(is_kadomatsu_sec(v[0][0], v[y1][x1], v[y2][x2])){
                
                dijkstra(G, dist, y2*w+x2 + w*h*((j+2)%4));
                for(int k=0; k<4; k++){
                    ans = min(ans, dist[ (h-1)*w+(w-1) + w*h*k ]+2);
                }
            }
            
        }
    }
    if(ans < INF) cout << ans << endl;
    else cout << -1 << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0