#include #include #include #include #include #include #include // 雪玉の「状態」を表す構造体State template 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 &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 struct StateHashGenerator { std::size_t operator()(const State& state) const { return ((std::hash()(state.size) ^ (std::hash()(state.row) << 1)) >> 1) ^ (std::hash()(state.column) << 1); } }; // 題意の条件が達成可能かを幅優先探索により判定する関数 template bool judge_by_bfs(T height, T width, State& start_state, State& goal_state, std::vector& stage) { constexpr int limit = 3000; constexpr T drs[4] = { 1, -1, 0, 0 }; constexpr T dcs[4] = { 0, 0, 1, -1 }; std::unordered_map, bool, StateHashGenerator> is_possible; is_possible[start_state] = true; std::queue> 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 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 start_state(start_size, start_row, start_column); int goal_size, goal_row, goal_column; std::cin >> goal_size >> goal_row >> goal_column; State goal_state(goal_size, goal_row, goal_column); std::vector stage; int snow_rows; 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; }