結果

問題 No.340 雪の足跡
ユーザー yudedakoyudedako
提出日時 2016-02-04 10:14:45
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 4,684 bytes
コンパイル時間 725 ms
コンパイル使用メモリ 75,568 KB
実行使用メモリ 20,352 KB
最終ジャッジ日時 2024-09-21 20:16:16
合計ジャッジ時間 4,623 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
10,752 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 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 3 ms
5,376 KB
testcase_13 AC 5 ms
5,376 KB
testcase_14 AC 57 ms
7,680 KB
testcase_15 AC 70 ms
7,972 KB
testcase_16 AC 40 ms
5,376 KB
testcase_17 AC 92 ms
8,704 KB
testcase_18 AC 77 ms
8,824 KB
testcase_19 AC 91 ms
8,832 KB
testcase_20 TLE -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <iostream>
#include <climits>
template <class T>
class Heap {
public:
	Heap(const int &n) :vector(n + 1), idx(0) {};
	void insert_value(const T &val) {
		vector.at(++idx) = val;
		bottom_up_normalize(idx);
	}
	T pop() {
		auto res = vector.at(1);
		vector.at(1) = vector.at(idx);
		vector.at(idx--) = vector.back();
		top_down_normalize(1);
		return res;
	}
	int size() const {
		return idx;
	}
	T top() const {
		return vector.at(1);
	}
private:
	std::vector<T> vector;
	int idx;
	void bottom_up_normalize(const int &i) {
		if (i != 1) {
			if (vector.at(i) < vector.at(i / 2)) {
				auto temp = vector.at(i / 2);
				vector.at(i / 2) = vector.at(i);
				vector.at(i) = temp;
				bottom_up_normalize(i / 2);
			}
		}
	}
	void top_down_normalize(const int &i) {
		int next = get(i);
		if (vector.at(next) < vector.at(i)) {
			auto temp = vector.at(next);
			vector.at(next) = vector.at(i);
			vector.at(i) = temp;
			top_down_normalize(next);
		}
	}
	int get(const int &n) const {
		if (n * 2 + 1 <= idx) {
			return (vector.at(n * 2 + 1) < vector.at(n * 2)) ? n * 2 + 1 : n * 2;
		}
		else if (n * 2 <= idx) {
			return n * 2;
		}
		else {
			return n;
		}
	}
};
class Cell {
public:
	Cell(const int &ax = 0, const int &ay = 0) :state{ 0 }, x{ ax }, y{ ay } {};
	bool is_neighbor(const Cell &other) const {
		return (abs(x - other.x) + abs(y - other.y)) == 1;
	}
	void set_path(Cell &from) {
		if (is_neighbor(from)) {
			if (x == from.x) {
				if (y > from.y) {
					state |= up;
					from.state |= down;
				}
				else {
					state |= down;
					from.state |= up;
				}
			}
			else {
				if (x > from.x) {
					state |= left;
					from.state |= right;
				}
				else {
					state |= right;
					from.state |= left;
				}
			}
		}
	}
	std::vector<std::pair<int, int>> get_neighbor() const {
		std::vector<std::pair<int, int>> res;
		for (const auto &p : { std::make_pair(x + 1, y), std::make_pair(x - 1, y), std::make_pair(x, y + 1), std::make_pair(x, y - 1) }) {
			if (has_path(p.first, p.second)) {
				res.push_back(p);
			}
		}
		return res;
	}
private:
	enum {
		right = 1, down = 2, left = 4, up = 8
	};
	int state;
	int x, y;
	int abs(const int &n) const {
		return n > 0 ? n : -n;
	}
	bool has_path(const int &cellx, const int &celly) const {
		if ((abs(x - cellx) + abs(y - celly)) == 1) {
			if (x == cellx) {
				if (y > celly) {
					return (state & up) != 0;
				}
				else {
					return (state & down) != 0;
				}
			}
			else {
				if (x > cellx) {
					return (state & left) != 0;
				}
				else {
					return (state & right) != 0;
				}
			}
		}
		else {
			return false;
		}
	}
};
struct Reach_time {
	int x, y;
	int time;
	Reach_time(const int &ax = 0, const int &ay = 0, const int &at = 0) :x{ ax }, y{ ay }, time{ at } {};
	bool operator<(const Reach_time &other) const {
		return time < other.time;
	}
};
int daijkstra(const std::vector<std::vector<Cell>> &map) {
	Heap<Reach_time> heap(map.size() * map.at(0).size() * 4);
	std::vector<std::vector<int>> memo(map.size(), std::vector<int>(map.at(0).size(), INT_MAX));
	heap.insert_value(Reach_time(0, 0, 0));
	memo.at(0).at(0) = 0;
	while (((heap.top().x != map.at(0).size() - 1) || (heap.top().y != map.size() - 1)) && heap.size() != 0) {
		auto rtime = heap.pop();
		const auto &cell = map.at(rtime.y).at(rtime.x);
		for (const auto &neighbor : cell.get_neighbor()) {
			if (memo.at(neighbor.second).at(neighbor.first) > rtime.time + 1) {
				memo.at(neighbor.second).at(neighbor.first) = rtime.time + 1;
				heap.insert_value(Reach_time(neighbor.first, neighbor.second, rtime.time + 1));
			}
		}
	}
	if (heap.size() == 0) {
		return -1;
	}
	else {
		return heap.top().time;
	}
}
int main() {
	int w, h, n;
	std::cin >> w >> h >> n;
	std::vector<std::vector<Cell>> map(h, std::vector<Cell>(w));
	for (auto y = 0; y < h; ++y) {
		for (auto x = 0; x < w; ++x) {
			map.at(y).at(x) = Cell(x, y);
		}
	}
	for (auto i = 0; i < n; ++i) {
		int m;
		std::cin >> m;
		int prev;
		std::cin >> prev;
		for (int b; m > 0; --m) {
			std::cin >> b;
			if (prev % w == b % w) {
				auto min = prev / w > b / w ? b / w : prev / w;
				auto max = prev / w > b / w ? prev / w : b / w;
				for (; min < max; ++min) {
					map.at(min).at(prev % w).set_path(map.at(min + 1).at(prev % w));
				}
			}
			else {
				auto min = prev % w > b % w ? b % w : prev % w;
				auto max = prev % w > b % w ? prev % w : b % w;
				for (; min < max; ++min) {
					map.at(prev / w).at(min).set_path(map.at(prev / w).at(min + 1));
				}
			}
			prev = b;
		}
	}
	auto res = daijkstra(map);
	if (res == -1) {
		std::cout << "Odekakedekinai.." << std::endl;
	}
	else {
		std::cout << res << std::endl;
	}
	return 0;
}
0