結果

問題 No.340 雪の足跡
コンテスト
ユーザー kapo
提出日時 2016-05-19 13:36:36
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,841 bytes
コンパイル時間 813 ms
コンパイル使用メモリ 79,388 KB
実行使用メモリ 15,104 KB
最終ジャッジ日時 2024-10-06 06:08:11
合計ジャッジ時間 13,534 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 28 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <queue>
#include <vector>
#include <map>

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
using namespace std;

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	int w, h, n, t1, t2, x1, y1, x2, y2, x, y, i, j;
	cin >> w >> h >> n;
	if(h == 1 && w == 1) { cout << 0 << endl; return 0; }
	vector<int> v;
	vector<vector<int> > lt;
	rep(i, 0, n) {
		v.clear();
		cin >> t1;
		rep(j, 0, t1+1) { cin >> t2; v.pb(t2); }
		lt.pb(v);
	}

	int bf[4] = {1,2,4,8}; // N E W S
	vector<vector<int> > dp(1000, vector<int>(1000, 0));
	vector<vector<int> > mp(1000, vector<int>(1000, 0));

	for(auto vec : lt) {
		rep(j, 0, (int)vec.size()-1) {
			y1 = vec[j]/w; x1 = vec[j]%w;
			y2 = vec[j+1]/w; x2 = vec[j+1]%w;
			if(y1 == y2) {
				if(x1 < x2) {
					rep(i,0,x2-x1) {
						mp[y1][x1+i] |= bf[1];
						mp[y1][x1+1+i] |= bf[2];
					}
				}
				else if(x1 > x2) {
					rep(i,0,x1-x2) {
						mp[y1][x1-i] |= bf[2];
						mp[y1][x1-1-i] |= bf[1];
					}
				}
			}
			else if(x1 == x2) {
				if(y1 < y2) {
					rep(i,0,y2-y1) {
						mp[y1+i][x1] |= bf[0];
						mp[y1+1+i][x1] |= bf[3];
					}
				}
				else if(y1 > y2) {
					rep(i,0,y1-y2) {
						mp[y1-i][x1] |= bf[3];
						mp[y1-1-i][x1] |= bf[0];
					}
				}
			}
		}
	}

	pair<int, int> p;
	queue<pair<int, int> > q;
	q.push(pair<int, int>(0,0));
	int ym[4] = {1, 0, 0, -1};
	int xm[4] = {0, 1, -1, 0};

	while(q.size()) {
		p = q.front();
		y = p.first; x = p.second;
		q.pop();

		rep(i,0,4) {
			if(!(mp[y][x] & bf[i])) continue;
			if(dp[y + ym[i]][x + xm[i]] == 0 || dp[ y+ym[i] ][ x+xm[i] ] > dp[y][x]+1) {
				dp[y + ym[i]][x + xm[i]] = dp[y][x] + 1;
				p.first = y+ym[i]; p.second = x+xm[i];
				q.push(p);
			}
		}
	}

	dp[h-1][w-1]? cout << dp[h-1][w-1] << endl : cout << "Odekakedekinai.." << endl;

	return 0;
}
0