結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 4 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 3 ms
5,248 KB
testcase_14 AC 22 ms
5,248 KB
testcase_15 AC 29 ms
5,248 KB
testcase_16 AC 21 ms
5,248 KB
testcase_17 AC 39 ms
5,248 KB
testcase_18 AC 30 ms
5,248 KB
testcase_19 AC 38 ms
5,248 KB
testcase_20 TLE -
testcase_21 AC 688 ms
5,248 KB
testcase_22 AC 8 ms
11,264 KB
testcase_23 AC 598 ms
11,392 KB
testcase_24 TLE -
testcase_25 AC 833 ms
11,264 KB
testcase_26 AC 60 ms
5,248 KB
testcase_27 AC 11 ms
5,248 KB
testcase_28 AC 53 ms
5,248 KB
testcase_29 AC 596 ms
8,064 KB
testcase_30 AC 345 ms
6,912 KB
testcase_31 AC 705 ms
10,624 KB
testcase_32 AC 760 ms
11,392 KB
testcase_33 AC 577 ms
11,392 KB
testcase_34 AC 755 ms
11,264 KB
testcase_35 TLE -
testcase_36 TLE -
権限があれば一括ダウンロードができます

ソースコード

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