結果

問題 No.323 yuki国
ユーザー はむ吉🐹はむ吉🐹
提出日時 2016-03-11 15:48:26
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,186 bytes
コンパイル時間 1,229 ms
コンパイル使用メモリ 82,612 KB
実行使用メモリ 5,076 KB
最終ジャッジ日時 2023-10-25 05:25:33
合計ジャッジ時間 9,131 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 WA -
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 12 ms
5,076 KB
testcase_06 AC 5 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 WA -
testcase_10 AC 2 ms
4,348 KB
testcase_11 WA -
testcase_12 AC 2 ms
4,348 KB
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
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 -- -
testcase_37 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdlib>
#include <ios>
#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>


// 雪玉の「状態」を表す構造体State
template <typename T> struct State {
	T size;
	T row;
	T column;
	State() {}
	State(T size, T row, T column) : size(size), row(row), column(column) {}
	bool operator==(const State<T> &other) const {
		return (size == other.size && row == other.row && column == other.column);
	}
};


// 構造体Stateのハッシュを求めるのに必要な構造体
// 上記のStateをunordered_mapのキーにするため、これを使う
// Reference: http://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key
template <typename T> struct StateHashGenerator {
	std::size_t operator()(const State<T>& state) const {
		return ((std::hash<T>()(state.size) ^ (std::hash<T>()(state.row) << 1)) >> 1) ^ (std::hash<T>()(state.column) << 1);
	}
};


// 題意の条件が達成可能かを幅優先探索により判定する関数
template <typename T> bool judge_by_bfs(T height, T width, State<T>& start_state, State<T>& goal_state, std::vector<std::string>& stage) {
	constexpr int limit = 3200;
	constexpr T drs[4] = { 1, -1, 0, 0 };
	constexpr T dcs[4] = { 0, 0, 1, -1 };
	std::unordered_map<State<T>, bool, StateHashGenerator<T>> is_possible;
	is_possible[start_state] = true;
	std::queue<State<T>> bfs_queue;
	bfs_queue.push(start_state);
	while (!bfs_queue.empty())
	{
		auto state0 = bfs_queue.front();
		bfs_queue.pop();
		if (state0 == goal_state)
		{
			break;
		}
		for (auto i = 0; i < 4; i++)
		{
			auto r = state0.row + drs[i];
			auto c = state0.column + dcs[i];
			if (r < 0 || r >= height || c < 0 || c >= width)
			{
				continue;
			}
			auto new_size = state0.size;
			if (stage[r][c] == '*')
			{
				new_size++;
			}
			else
			{
				new_size--;
			}
			if (new_size <= 0 || new_size > limit)
			{
				continue;
			}
			State<T> next_state(new_size, r, c);
			if (is_possible[next_state])
			{
				continue;
			}
			is_possible[next_state] = true;
			bfs_queue.push(next_state);
		}
	}
	return is_possible[goal_state];
}


int main()
{
	const std::string snow("*");
	// 入出力を高速化する
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	// 入力の読み込み
	int height, width;
	std::cin >> height >> width;
	int start_size, start_row, start_column;
	std::cin >> start_size >> start_row >> start_column;
	State<int> start_state(start_size, start_row, start_column);
	int goal_size, goal_row, goal_column;
	std::cin >> goal_size >> goal_row >> goal_column;
	State<int> goal_state(goal_size, goal_row, goal_column);
	std::vector<std::string> stage;
	int snow_rows = 0;
	for (auto i = 0; i < height; i++) {
		std::string row_str;
		std::cin >> row_str;
		stage.push_back(row_str);
		auto pos = row_str.find(snow);
		if (pos != std::string::npos)
		{
			snow_rows++;
		}
	}
	// 判定
	bool answer = true;
	if ((goal_size - start_size) > snow_rows * width)
	{
		answer = false;
	}
	else
	{
		answer = judge_by_bfs(height, width, start_state, goal_state, stage);
	}
	std::cout << (answer ? "Yes" : "No") << std::endl;
	return EXIT_SUCCESS;
}
0