結果

問題 No.340 雪の足跡
コンテスト
ユーザー masa
提出日時 2016-01-29 23:48:18
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,047 bytes
コンパイル時間 832 ms
コンパイル使用メモリ 80,912 KB
実行使用メモリ 15,116 KB
最終ジャッジ日時 2024-09-21 18:49:56
合計ジャッジ時間 13,185 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 28 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
#include <queue>
#include <sstream>
#include <bitset>

using namespace std;

const int UP = 1;
const int DOWN = 1 << 1;
const int RIGHT = 1 << 2;
const int LEFT = 1 << 3;

const int INF = 1e9;

string bin_str(int n) {
	stringstream ss;
	ss << static_cast<std::bitset<4> >(n);
	return ss.str();
}

int main() {
	int w, h, n, m, in_b;

	cin >> w >> h >> n;

	vector<vector<int>> b(n);
	for (int i = 0; i < n; i++) {
		cin >> m;
		for (int j = 0; j <= m; j++) {
			cin >> in_b;
			b[i].emplace_back(in_b);
		}
	}

	// up down right left の順にbit
	vector<int> connect(w * h, 0);
	for (int i = 0; i < n; i++) {
		if (b[i].size() < 2) {
			continue;
		}

		for (int j = 1; j < b[i].size(); j++) {
			int big = max(b[i][j - 1], b[i][j]);
			int small = min(b[i][j - 1], b[i][j]);

			if (big - small < w) {
				connect[small] |= RIGHT;
				connect[big] |= LEFT;
				for (int k = small + 1; k < big; k++) {
					connect[k] |= (RIGHT | LEFT);
				}
			} else {
				connect[small] |= UP;
				connect[big] |= DOWN;
				for (int k = small + w; k < big; k += w) {
					connect[k] |= (UP | DOWN);
				}
			}
		}
	}

	// for (int i = 0; i < w * h; i++) {
	// 	printf("connect %d %s\n", i, bin_str(connect[i]).c_str());
	// }

	vector<int> memo(w * h, 1e9);
	queue<int> que;
	int goal = w * h - 1;
	memo[0] = 0;
	que.push(0);

	int masks[4]   = {UP, DOWN, RIGHT, LEFT};
	int to_next[4] = {w,  -w,   1,     -1};
	while (!que.empty()) {
		auto place = que.front();
		que.pop();

// printf("place %d\n", place);

		if (place == goal) {
			break;
		}

		for (int i = 0; i < 4; i++) {
			if (connect[place] & masks[i]) {
				auto next = place + to_next[i];
// printf("next %d %d\n", next, memo[next]);
				if (memo[next] > memo[place] + 1) {
					que.push(place + to_next[i]);
					memo[next] = memo[place] + 1;
				}
			}
		}
	}

	if (memo[goal] == INF) {
		cout << "Odekakedekinai.." << endl;
	} else {
		cout << memo[goal] << endl;
	}
	return 0;
}
0