# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
241879 | NONAME | Jetpack (COCI16_jetpack) | C++14 | 35 ms | 10744 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
int n, m, d[10][int(1e5) + 10], pr[10][int(1e5) + 10];
char c[10][int(1e5) + 10];
queue <pair <int, int> > q;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef _LOCAL
freopen("in", "r", stdin);
freopen("out", "w", stdout);
#endif // _LOCAL
cin >> m;
n = 10;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> c[i][j];
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
d[i][j] = 2 * m, pr[i][j] = -1;
q.push(make_pair(n - 1, 0));
d[n - 1][0] = 0;
while (!q.empty()) {
auto o = q.front();
q.pop();
if (o.second == m - 1)
continue;
if (o.first == n - 1 || o.first == 0) {
if (c[o.first][o.second + 1] != 'X' && d[o.first][o.second + 1] > d[o.first][o.second] + 1) {
q.push(make_pair(o.first, o.second + 1));
d[o.first][o.second + 1] = d[o.first][o.second] + 1;
pr[o.first][o.second + 1] = o.first;
}
}
if (o.first != 0) {
if (c[o.first - 1][o.second + 1] != 'X' && d[o.first - 1][o.second + 1] > d[o.first][o.second] + 1) {
q.push(make_pair(o.first - 1, o.second + 1));
d[o.first - 1][o.second + 1] = d[o.first][o.second] + 1;
pr[o.first - 1][o.second + 1] = o.first;
}
}
if (o.first != n - 1) {
if (c[o.first + 1][o.second + 1] != 'X' && d[o.first + 1][o.second + 1] > d[o.first][o.second] + 1) {
q.push(make_pair(o.first + 1, o.second + 1));
d[o.first + 1][o.second + 1] = d[o.first][o.second] + 1;
pr[o.first + 1][o.second + 1] = o.first;
}
}
}
int p = -1;
for (int i = 0; i < n; ++i)
if (pr[i][m - 1] != -1 && (p == -1 || d[i][m - 1] < d[p][m - 1]))
p = i;
vector <pair <int, int> > res;
res.clear();
int lst = p, t = m - 2;
int cr = pr[p][m - 1];
while (cr != -1) {
if (cr - 1 == lst)
res.push_back(make_pair(t, 1));
--t;
lst = cr;
cr = pr[cr][t + 1];
}
sort(res.begin(), res.end());
cout << int(res.size()) << "\n";
for (auto i : res)
cout << i.first << " " << i.second << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |