結果

問題 No.340 雪の足跡
ユーザー IL_msta
提出日時 2017-05-23 01:25:09
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 413 ms / 1,000 ms
コード長 2,998 bytes
コンパイル時間 1,183 ms
コンパイル使用メモリ 112,776 KB
実行使用メモリ 69,812 KB
最終ジャッジ日時 2024-09-19 10:36:25
合計ジャッジ時間 7,979 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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

#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>
#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18;
const double PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;
vector< vector<int> > Gra;
vector<int> dist;
void solve(){
    int W,H,N;
    cin >> W >> H >> N;
    Gra = vector< vector<int> >(W*H);
    vector< vector<int> > RR(W,vector<int>(H+1,0));
    vector< vector<int> > CC(H,vector<int>(W+1,0));
    for(int i=0;i<N;++i){//10^3
        int M;
        cin >> M;
        ++M;
        vector<int> B(M);
        for(int j=0;j<M;++j){
            cin >> B[j];
        }
        for(int j=1;j<M;++j){//10^3
            int u,v;
            u = B[j-1];
            v = B[j];
            if( u > v ){
                swap(u,v);
            }
            if( u%W == v%W ){//縦移動RR
                int rank = u%W;
                RR[rank][u/W]++;
                RR[rank][(v/W)]--;
                /*for(int k=u+W;k<=v;k+=W){
                    Gra[k-W].push_back(k);
                    Gra[k].push_back(k-W);
                }*/
            }else{//横移動CC
                int rank = u/W;
                CC[rank][u%W]++;
                CC[rank][(v%W)]--;
                /*for(int k=u+1;k<=v;++k){
                    Gra[k-1].push_back(k);
                    Gra[k].push_back(k-1);
                }*/
            }
        }
    }
    for(int c=0;c<W;++c){
        if( RR[c][0] > 0 ){
            Gra[0*W+c].push_back(1*W+c);
            Gra[1*W+c].push_back(0*W+c);
        }
        for(int r=1;r<H-1;++r){
            RR[c][r]+= RR[c][r-1];
            if( RR[c][r] > 0 ){
                Gra[r*W+c].push_back((r+1)*W+c);
                Gra[(r+1)*W+c].push_back(r*W+c);
            }
        }
    }
    for(int r=0;r<H;++r){
        if( CC[r][0] > 0 ){
            Gra[r*W+0].push_back(r*W+1);
            Gra[r*W+1].push_back(r*W+0);
        }
        for(int c=1;c<W-1;++c){
            CC[r][c] += CC[r][c-1];
            if( CC[r][c] > 0 ){
                Gra[r*W+c].push_back(r*W+c+1);
                Gra[r*W+c+1].push_back(r*W+c);
            }
        }
    }
    dist = vector<int>(W*H,INF);
    vector<bool> visit(W*H, false);
    queue<int> que;
    que.push(0);//スタート地点
    visit[0] = true;
    dist[0] = 0;
    
    while(!que.empty()){
        int now = que.front();que.pop();
        int size = Gra[now].size();
        for(int i=0;i<size;++i){
            int to = Gra[now][i];
            if( visit[to] == true ) continue;
            visit[to] = true;
            dist[to] = dist[now] + 1;
            que.push( to );
        }
    }
    if( dist[W*H-1] == INF ){
        cout << "Odekakedekinai.." << endl;
    }else{
        cout << dist[W*H-1] << endl;
    }
}
#pragma region main
signed main(void){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//小数を10進数表示
    cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別   
    
    solve();
}
#pragma endregion //main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0