結果

問題 No.323 yuki国
ユーザー はむ吉🐹
提出日時 2016-03-11 13:37:24
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,943 bytes
コンパイル時間 866 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 23,416 KB
最終ジャッジ日時 2024-09-25 00:17:26
合計ジャッジ時間 7,670 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 2 TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

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()
{
	// 入出力を高速化する
	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;
	for (auto i = 0; i < height; i++) {
		std::string row_str;
		std::cin >> row_str;
		stage.push_back(row_str);
	}
	// 判定
	auto answer = judge_by_bfs(height, width, start_state, goal_state, stage);
	std::cout << (answer ? "Yes" : "No") << std::endl;
	return EXIT_SUCCESS;
}
0