Submission #1352754
Source Code Expand
#include "iostream" #include "climits" #include "list" #include "queue" #include "stack" #include "set" #include "functional" #include "algorithm" #include "math.h" #include "utility" #include "string" #include "map" #include "unordered_map" #include "iomanip" #include "random" using namespace std; const long long int MOD = 1000000007; list<long long int> Prime(int M) { list<long long int>P; P.push_back(2); P.push_back(3); for (int i = 5; i <= M; i += 6) { bool flag = true; for (auto j : P) { if (i%j == 0) { flag = false; break; } } if (flag)P.push_back(i); flag = true; for (auto j : P) { if ((i + 2) % j == 0) { flag = false; break; } } if (flag)P.push_back(i + 2); } return P; } long long int N, M, K, Q, W, H; long long int ans; int main() { ios::sync_with_stdio(false); cin >> H >> W; int sx, sy, gx, gy; cin >> sy >> sx; cin >> gy >> gx; string s[100]; for (int i = 1; i <= H; i++) { cin >> s[i]; s[i] = "#" + s[i] + "#"; } for (int i = 0; i <= W + 1; i++) { s[0].push_back('#'); s[H+1].push_back('#'); } int d[] = { 1,0,-1,0,1 }; int dis[100][100] = {}; for (int i = 0; i < 100; i++) { for (int j = 0; j < 100; j++)dis[i][j] = 100000; } dis[sy][sx] = 0; queue<pair<int, int> >Q; Q.push({ sy,sx }); while (!Q.empty()) { int cy = Q.front().first; int cx = Q.front().second; for (int i = 0; i < 4; i++) { if (s[cy + d[i]][cx + d[i + 1]] == '.'&&dis[cy][cx] + 1 < dis[cy + d[i]][cx + d[i + 1]]) { dis[cy + d[i]][cx + d[i + 1]] = dis[cy][cx] + 1; Q.push({ cy + d[i],cx + d[i + 1] }); } } Q.pop(); } cout << dis[gy][gx] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 幅優先探索 |
User | olphe |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1739 Byte |
Status | AC |
Exec Time | 1 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 | 1 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 | 1 ms | 256 KB |
subtask1_05.txt | AC | 1 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 | 1 ms | 256 KB |
subtask1_10.txt | AC | 1 ms | 256 KB |
subtask1_11.txt | AC | 1 ms | 256 KB |
subtask1_12.txt | AC | 1 ms | 256 KB |
subtask1_13.txt | AC | 1 ms | 256 KB |
subtask1_14.txt | AC | 1 ms | 256 KB |
subtask1_15.txt | AC | 1 ms | 256 KB |
subtask1_16.txt | AC | 1 ms | 256 KB |
subtask1_17.txt | AC | 1 ms | 256 KB |
subtask1_18.txt | AC | 1 ms | 256 KB |
subtask1_19.txt | AC | 1 ms | 256 KB |
subtask1_20.txt | AC | 1 ms | 256 KB |
subtask1_21.txt | AC | 1 ms | 256 KB |
subtask1_22.txt | AC | 1 ms | 256 KB |