結果

問題 No.340 雪の足跡
ユーザー masamasa
提出日時 2016-01-29 23:48:18
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 3 ms
5,376 KB
testcase_14 AC 20 ms
5,376 KB
testcase_15 AC 27 ms
5,376 KB
testcase_16 AC 19 ms
5,376 KB
testcase_17 AC 33 ms
5,376 KB
testcase_18 AC 24 ms
5,376 KB
testcase_19 AC 33 ms
5,376 KB
testcase_20 TLE -
testcase_21 AC 882 ms
7,424 KB
testcase_22 AC 6 ms
10,880 KB
testcase_23 AC 676 ms
15,052 KB
testcase_24 TLE -
testcase_25 AC 671 ms
15,044 KB
testcase_26 AC 55 ms
5,376 KB
testcase_27 AC 10 ms
5,376 KB
testcase_28 AC 51 ms
5,376 KB
testcase_29 AC 536 ms
11,264 KB
testcase_30 AC 317 ms
9,984 KB
testcase_31 AC 561 ms
13,716 KB
testcase_32 AC 690 ms
15,104 KB
testcase_33 AC 524 ms
14,976 KB
testcase_34 AC 697 ms
15,116 KB
testcase_35 TLE -
testcase_36 TLE -
権限があれば一括ダウンロードができます

ソースコード

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