Submission #3632635
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
void f(int y, int x, vector<string>& X, vector<vector<int>>& D, queue<pair<int, int>>& Q, int d) {
if (y < 0 || x < 0 || y == X.size() || x == X[0].size()) return;
if (X[y][x] == '#' || D[y][x] != -1) return;
D[y][x] = d + 1;
Q.push(make_pair(y, x));
}
int main() {
int R, C, sy, sx, gy, gx;
cin >> R >> C >> sy >> sx >> gy >> gx;
sy--; sx--; gy--; gx--;
vector<string> X(R);
vector<vector<int>> D(R);
for (int i = 0; i < R; i++) {
string x;
cin >> X[i];
for (int j = 0; j < C; j++) {
D[i].push_back(-1);
}
}
queue<pair<int, int>> Q;
Q.push(make_pair(sy, sx)); D[sy][sx] = 0;
while (Q.size()) {
auto p = Q.front(); Q.pop();
int y = p.first, x = p.second;
if (y == gy && x == gx) break;
int d = D[y][x];
f(y-1, x, X, D, Q, d);
f(y+1, x, X, D, Q, d);
f(y, x-1, X, D, Q, d);
f(y, x+1, X, D, Q, d);
}
cout << D[gy][gx] << endl;
}
Submission Info
Submission Time |
|
Task |
C - 幅優先探索 |
User |
skwbc |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
997 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 |
2 ms |
256 KB |
subtask1_02.txt |
AC |
2 ms |
256 KB |
subtask1_03.txt |
AC |
2 ms |
256 KB |
subtask1_04.txt |
AC |
2 ms |
256 KB |
subtask1_05.txt |
AC |
2 ms |
256 KB |
subtask1_06.txt |
AC |
2 ms |
256 KB |
subtask1_07.txt |
AC |
1 ms |
256 KB |
subtask1_08.txt |
AC |
2 ms |
256 KB |
subtask1_09.txt |
AC |
2 ms |
256 KB |
subtask1_10.txt |
AC |
2 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 |
2 ms |
256 KB |
subtask1_20.txt |
AC |
2 ms |
256 KB |
subtask1_21.txt |
AC |
2 ms |
256 KB |
subtask1_22.txt |
AC |
2 ms |
256 KB |