結果

問題 No.340 雪の足跡
コンテスト
ユーザー tsukio
提出日時 2016-06-09 23:27:38
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,262 bytes
コンパイル時間 662 ms
コンパイル使用メモリ 74,500 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-10-09 08:12:44
合計ジャッジ時間 15,018 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 28 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

const int DIR_NONE = 0;
const int DIR_LEFT = 1;
const int DIR_UP = 2;
const int DIR_RIGHT = 4;
const int DIR_DOWN = 8;

struct Node {
	int y;
	int x;
	int cost;
};

struct DirInfo {
	int dir;
	int dy;
	int dx;
};

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

	vector<vector<int>> town(h);
	for (auto& row : town) {
		row.resize(w, DIR_NONE);
	}

	for (int i = 0; i < n; i++) {
		int stop_count, current_no;
		cin >> stop_count >> current_no;

		for (int k = 0; k < stop_count; k++) {
			int next_no, small_no, large_no;
			cin >> next_no;

			if (current_no > next_no) {
				small_no = next_no;
				large_no = current_no;
			}
			else {
				small_no = current_no;
				large_no = next_no;
			}

			int sy = small_no / w;
			int sx = small_no - sy * w;
			int ly = large_no / w;
			int lx = large_no - ly * w;

			if ((large_no - small_no) % w == 0) {
				town[sy][sx] |= DIR_DOWN;
				town[ly][sx] |= DIR_UP;
				for (int m = sy + 1; m <= ly - 1; m++) {
					town[m][sx] |= DIR_UP | DIR_DOWN;
				}
			}
			else {
				town[sy][sx] |= DIR_RIGHT;
				town[sy][lx] |= DIR_LEFT;
				for (int m = sx + 1; m <= lx - 1; m++) {
					town[sy][m] |= DIR_LEFT | DIR_RIGHT;
				}
			}

			current_no = next_no;
		}
	}

	vector<vector<int>> dp(h);
	for (auto& row : dp) {
		row.resize(w, INT_MAX);
	}
	dp[0][0] = 0;

	vector<DirInfo> dirs = { 
		DirInfo { DIR_LEFT, 0, -1},
		DirInfo { DIR_UP, -1, 0},
		DirInfo { DIR_RIGHT, 0, 1},
		DirInfo { DIR_DOWN, 1, 0}
	};

	queue<Node> nodes;
	nodes.emplace(Node{ 0, 0, 0 });

	while (!nodes.empty()) {
		Node node = nodes.front(); nodes.pop();

		for (int i = 0; i < dirs.size(); i++) {
			DirInfo info = dirs[i];

			int ny = node.y + info.dy;
			int nx = node.x + info.dx;

			if (ny < 0 || ny >= h || nx < 0 || nx >= w)
				continue;

			if ((town[node.y][node.x] & info.dir) == 0)
				continue;

			int next_cost = node.cost + 1;

			if (dp[ny][nx] <= next_cost)
				continue;

			dp[ny][nx] = next_cost;
			nodes.emplace(Node{ ny, nx, next_cost });
		}
	}

	int result = dp[h - 1][w - 1];
	if (result == INT_MAX) {
		cout << "Odekakedekinai.." << endl;
	}
	else {
		cout << result << endl;
	}

	return 0;
}
0