結果

問題 No.340 雪の足跡
ユーザー IL_mstaIL_msta
提出日時 2017-05-23 01:25:09
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 450 ms / 1,000 ms
コード長 2,998 bytes
コンパイル時間 1,103 ms
コンパイル使用メモリ 114,024 KB
実行使用メモリ 69,676 KB
最終ジャッジ日時 2023-10-19 14:28:15
合計ジャッジ時間 8,792 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 1 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 3 ms
4,348 KB
testcase_12 AC 3 ms
4,348 KB
testcase_13 AC 3 ms
4,348 KB
testcase_14 AC 28 ms
8,120 KB
testcase_15 AC 32 ms
8,384 KB
testcase_16 AC 15 ms
5,568 KB
testcase_17 AC 38 ms
9,176 KB
testcase_18 AC 36 ms
9,176 KB
testcase_19 AC 36 ms
9,176 KB
testcase_20 AC 166 ms
44,596 KB
testcase_21 AC 75 ms
4,348 KB
testcase_22 AC 23 ms
38,688 KB
testcase_23 AC 232 ms
69,676 KB
testcase_24 AC 121 ms
38,788 KB
testcase_25 AC 208 ms
52,252 KB
testcase_26 AC 23 ms
4,348 KB
testcase_27 AC 6 ms
4,348 KB
testcase_28 AC 28 ms
6,272 KB
testcase_29 AC 292 ms
41,836 KB
testcase_30 AC 216 ms
32,664 KB
testcase_31 AC 380 ms
63,936 KB
testcase_32 AC 447 ms
69,676 KB
testcase_33 AC 409 ms
69,676 KB
testcase_34 AC 450 ms
69,676 KB
testcase_35 AC 415 ms
69,676 KB
testcase_36 AC 417 ms
69,676 KB
権限があれば一括ダウンロードができます

ソースコード

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