#include #include #include #include #include // 進める方位の数 constexpr std::size_t NUM_DS = 4; // タテ方向に進める数 constexpr int DRS[NUM_DS] = { 1, -1, 0, 0 }; // 横方向に進める数 constexpr int DCS[NUM_DS] = { 0, 0, 1, -1 }; // 考慮する雪玉のサイズの最大値 constexpr int MAX_SIZE = 3000; // 空き地を格納する文字列の配列 typedef std::vector Stage; // 各状態が訪問済みかを記録するテーブル typedef std::vector>> Visited; // 幅優先探索で扱う状態を表すクラス class State { private: int m_size; int m_row; int m_column; public: State(const int& size, const int& row, const int& column) : m_size(size), m_row(row), m_column(column) { } // 状態の各要素を変数に書き出す // std::tieもどき void readState(int& size, int& row, int& column) const { size = m_size; row = m_row; column = m_column; } // 演算子オーバーロード (==) bool operator==(const State& other) const { return m_size == other.m_size && m_row == other.m_row && m_column == other.m_column; } // 演算子オーバーロード (!=) bool operator!=(const State& other) const { return !(*this == other); } }; // 与えられたテーブルによると、与えられた状態は訪問済みか? bool check_visit(const Visited& is_visited, const State& state) { int size, row, column; state.readState(size, row, column); return is_visited[size][row][column]; } // 与えられた状態が訪問済みであることを、与えられたテーブルに書き込む void record_visit(Visited& is_visited, const State& state) { int size, row, column; state.readState(size, row, column); is_visited[size][row][column] = true; } // 幅優先探索により、題意の判定を行う bool judge_by_bfs(const int& height, const int& width, const State& start_state, const State& goal_state, const Stage& stage) { Visited is_visited(MAX_SIZE, std::vector>(height, std::vector(width, false))); std::queue queue; queue.push(start_state); record_visit(is_visited, start_state); while (!queue.empty()) { auto state0 = queue.front(); int size0, row0, column0; state0.readState(size0, row0, column0); queue.pop(); if (state0 == goal_state) { break; } for (auto i = 0; i < NUM_DS; i++) { auto row = row0 + DRS[i]; auto column = column0 + DCS[i]; // 空き地からはみ出してはならない if (row < 0 || row >= height || column < 0 || column >= width) { continue; } auto size = size0 + (stage[row][column] == '*' ? 1 : -1); // 雪玉がとけたり大きくなりすぎたりしてはならない if (size <= 0 || size >= MAX_SIZE) { continue; } // 訪問済みならスキップする if (is_visited[size][row][column]) { continue; } is_visited[size][row][column] = true; queue.push(State(size, row, column)); } } return check_visit(is_visited, goal_state); } int main() { // 入力の高速化 std::cin.tie(nullptr); 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); Stage stage; for (auto i = 0; i < height; i++) { std::string row; std::cin >> row; stage.push_back(row); } // 判定 auto answer = judge_by_bfs(height, width, start_state, goal_state, stage); std::cout << (answer ? "Yes" : "No") << std::endl; return EXIT_SUCCESS; }