結果
問題 | 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 |
ソースコード
#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; }