結果

問題 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 #
raw source code 

#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()
0