Submission #3971581
Source Code Expand
// Last Change: 01/10/2019 17:17:43. #include <algorithm> #include <array> #include <bitset> #include <cmath> #include <cstdlib> #include <iomanip> #include <iostream> #include <list> #include <map> #include <memory> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; using ll = long long; void LoopUntilZeroInpput() { int hogegegege = 0; while (cin >> hogegegege && hogegegege != 0) { } } struct Point { int x, y; bool operator==(const Point &another) { return this->x == another.x and this->y == another.y; } void combine(const Point &another, int y, int x) { this->y = another.y + y; this->x = another.x + x; } }; class Cal { private: int R, C; Point start, goal; vector<vector<char>> field; vector<vector<int>> memo; void Input(); void Solve(); void Output(); void MakeField(); public: void Main(); }; void Cal::MakeField() { vector<char> input(C); for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { cin >> input[j]; } field.push_back(input); } } void Cal::Input() { cin >> R >> C; cin >> start.y >> start.x; cin >> goal.y >> goal.x; --start.y; --start.x; --goal.y; --goal.x; field.reserve(R); MakeField(); } void Cal::Solve() { memo.reserve(R); for (int i = 0; i < R; i++) { vector<int> init(C, 0); memo.push_back(init); } memo[start.y][start.x] = 0; Point curPos, next; queue<Point> q; q.push(start); while (q.size() > 0) { curPos = q.front(); q.pop(); if (curPos == goal) { return; } //下 next.combine(curPos, 1, 0); if (field[next.y][next.x] == '.' && memo[next.y][next.x] == 0) { q.push(next); memo[next.y][next.x] = memo[curPos.y][curPos.x] + 1; } //右 next.combine(curPos, 0, 1); if (field[next.y][next.x] == '.' && memo[next.y][next.x] == 0) { q.push(next); memo[next.y][next.x] = memo[curPos.y][curPos.x] + 1; } //左 next.combine(curPos, 0, -1); if (field[next.y][next.x] == '.' && memo[next.y][next.x] == 0) { q.push(next); memo[next.y][next.x] = memo[curPos.y][curPos.x] + 1; } //上 next.combine(curPos, -1, 0); if (field[next.y][next.x] == '.' && memo[next.y][next.x] == 0) { q.push(next); memo[next.y][next.x] = memo[curPos.y][curPos.x] + 1; } } } void Cal::Output() { // x,yに注意 int ans = memo[goal.y][goal.x]; if (ans == 0) { cout << -1 << endl; } else { cout << ans << endl; } } void Cal::Main() { Input(); Solve(); Output(); } int main() { unique_ptr<Cal> cal(new Cal()); cal->Main(); //LoopUntilZeroInpput(); }
Submission Info
Submission Time | |
---|---|
Task | C - 幅優先探索 |
User | Nagatuki |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2839 Byte |
Status | AC |
Exec Time | 2 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt |
All | subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample01.txt | AC | 1 ms | 256 KB |
subtask0_sample02.txt | AC | 1 ms | 256 KB |
subtask0_sample03.txt | AC | 2 ms | 256 KB |
subtask1_01.txt | AC | 1 ms | 256 KB |
subtask1_02.txt | AC | 1 ms | 256 KB |
subtask1_03.txt | AC | 1 ms | 256 KB |
subtask1_04.txt | AC | 2 ms | 256 KB |
subtask1_05.txt | AC | 2 ms | 256 KB |
subtask1_06.txt | AC | 1 ms | 256 KB |
subtask1_07.txt | AC | 1 ms | 256 KB |
subtask1_08.txt | AC | 1 ms | 256 KB |
subtask1_09.txt | AC | 2 ms | 256 KB |
subtask1_10.txt | AC | 1 ms | 256 KB |
subtask1_11.txt | AC | 2 ms | 256 KB |
subtask1_12.txt | AC | 2 ms | 256 KB |
subtask1_13.txt | AC | 2 ms | 256 KB |
subtask1_14.txt | AC | 1 ms | 256 KB |
subtask1_15.txt | AC | 2 ms | 256 KB |
subtask1_16.txt | AC | 2 ms | 256 KB |
subtask1_17.txt | AC | 2 ms | 256 KB |
subtask1_18.txt | AC | 2 ms | 256 KB |
subtask1_19.txt | AC | 1 ms | 256 KB |
subtask1_20.txt | AC | 1 ms | 256 KB |
subtask1_21.txt | AC | 2 ms | 256 KB |
subtask1_22.txt | AC | 1 ms | 256 KB |