結果

問題 No.323 yuki国
コンテスト
ユーザー はむ吉🐹
提出日時 2016-05-21 19:14:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 223 ms / 5,000 ms
コード長 4,267 bytes
コンパイル時間 994 ms
コンパイル使用メモリ 87,544 KB
実行使用メモリ 14,208 KB
最終ジャッジ日時 2024-06-28 12:32:24
合計ジャッジ時間 4,051 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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


// 進める方位の数
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<std::string> Stage;
// 各状態が訪問済みかを記録するテーブル
typedef std::vector<std::vector<std::vector<bool>>> 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<std::vector<bool>>(height, std::vector<bool>(width, false)));
    std::queue<State> 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;
}
0