結果

問題 No.340 雪の足跡
ユーザー masamasa
提出日時 2016-07-08 12:24:08
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 242 ms / 1,000 ms
コード長 2,595 bytes
コンパイル時間 1,811 ms
コンパイル使用メモリ 87,340 KB
実行使用メモリ 18,720 KB
最終ジャッジ日時 2023-08-03 01:19:10
合計ジャッジ時間 7,777 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 1 ms
4,384 KB
testcase_02 AC 1 ms
4,384 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,384 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,384 KB
testcase_08 AC 2 ms
4,384 KB
testcase_09 AC 1 ms
4,384 KB
testcase_10 AC 1 ms
4,384 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,384 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 9 ms
4,384 KB
testcase_15 AC 11 ms
4,464 KB
testcase_16 AC 8 ms
4,380 KB
testcase_17 AC 13 ms
4,464 KB
testcase_18 AC 11 ms
4,384 KB
testcase_19 AC 14 ms
4,624 KB
testcase_20 AC 120 ms
18,608 KB
testcase_21 AC 79 ms
4,384 KB
testcase_22 AC 16 ms
18,688 KB
testcase_23 AC 131 ms
18,716 KB
testcase_24 AC 115 ms
18,644 KB
testcase_25 AC 123 ms
18,720 KB
testcase_26 AC 20 ms
4,384 KB
testcase_27 AC 5 ms
4,380 KB
testcase_28 AC 18 ms
4,384 KB
testcase_29 AC 136 ms
12,020 KB
testcase_30 AC 94 ms
10,004 KB
testcase_31 AC 187 ms
17,300 KB
testcase_32 AC 242 ms
18,588 KB
testcase_33 AC 153 ms
18,620 KB
testcase_34 AC 188 ms
18,536 KB
testcase_35 AC 138 ms
18,636 KB
testcase_36 AC 139 ms
18,668 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;

typedef pair<int, int> PII;

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

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

void show(vector<int> &v) {
	for (auto e : v) {
		printf("%2d ", e);
	}
	printf("\n");
}

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

	scanf("%d %d %d", &w, &h, &n);

	vector<int> horizontal(w*h, 0);
	vector<int> vertical(w*h, 0);

	for (int i = 0; i < n; i++) {
		int m, b, b_prev;
		scanf("%d %d", &m, &b_prev);
		for (int j = 1; j <= m; j++) {
			scanf("%d", &b);

			int big = max(b, b_prev);
			int small = min(b, b_prev);

			if (big - small < w) {
				horizontal[small] += 1;
				horizontal[big] -= 1;
			} else {
				vertical[small] += 1;
				vertical[big] -= 1;
			}

			b_prev = b;
		}
	}

	// show(horizontal);
	// show(vertical);

	vector<int> connect(w * h, 0);

	for (int i = 0; i < h; i++) {
		int l = i * w;
		int r = (i + 1) * w - 1;

		// printf("lr %d %d\n", r, l);

		int ok_right = 0;
		for (int j = l; j <= r; j++) {
			ok_right += horizontal[j];
			if (ok_right > 0) {
				connect[j] |= RIGHT;
			}
		}
		int ok_left = 0;
		for (int j = r; j >= l; j--) {
			ok_left += horizontal[j];
			if (ok_left < 0) {
				connect[j] |= LEFT;
			}
		}
	}

	for (int i = 0; i < w; i++) {
		int d = i;
		int u = (h - 1) * w + i;

		int ok_up = 0;
		for (int j = d; j <= u; j += w) {
			ok_up += vertical[j];
			if (ok_up > 0) {
				connect[j] |= UP;
			}
		}
		int ok_down = 0;
		for (int j = u; j >= d; j -= w) {
			ok_down += vertical[j];
			if (ok_down < 0) {
				connect[j] |= 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, -1);
	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 now = que.front();
		que.pop();

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

		if (now == goal) {
			break;
		}

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

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