結果

問題 No.323 yuki国
ユーザー はむ吉🐹はむ吉🐹
提出日時 2016-05-21 19:14:53
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 229 ms / 5,000 ms
コード長 4,267 bytes
コンパイル時間 1,232 ms
コンパイル使用メモリ 86,548 KB
実行使用メモリ 14,344 KB
最終ジャッジ日時 2023-09-10 21:28:57
合計ジャッジ時間 4,672 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 3 ms
4,384 KB
testcase_02 AC 3 ms
4,384 KB
testcase_03 AC 5 ms
5,272 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 4 ms
4,384 KB
testcase_06 AC 3 ms
4,380 KB
testcase_07 AC 4 ms
4,536 KB
testcase_08 AC 154 ms
14,056 KB
testcase_09 AC 80 ms
14,208 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 3 ms
4,384 KB
testcase_13 AC 78 ms
14,100 KB
testcase_14 AC 155 ms
14,344 KB
testcase_15 AC 73 ms
14,144 KB
testcase_16 AC 128 ms
14,076 KB
testcase_17 AC 86 ms
14,220 KB
testcase_18 AC 15 ms
8,616 KB
testcase_19 AC 118 ms
11,744 KB
testcase_20 AC 38 ms
14,124 KB
testcase_21 AC 229 ms
14,136 KB
testcase_22 AC 54 ms
14,100 KB
testcase_23 AC 228 ms
14,100 KB
testcase_24 AC 41 ms
14,064 KB
testcase_25 AC 86 ms
14,216 KB
testcase_26 AC 41 ms
14,120 KB
testcase_27 AC 195 ms
14,124 KB
testcase_28 AC 93 ms
14,140 KB
testcase_29 AC 85 ms
14,080 KB
testcase_30 AC 3 ms
4,380 KB
testcase_31 AC 3 ms
4,380 KB
testcase_32 AC 3 ms
4,380 KB
testcase_33 AC 2 ms
4,380 KB
testcase_34 AC 3 ms
4,380 KB
testcase_35 AC 2 ms
4,384 KB
testcase_36 AC 3 ms
4,380 KB
testcase_37 AC 3 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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