#include <bits/stdc++.h>
#ifndef dbg
#define dbg(...)
#endif
#define all(x) begin(x), end(x)
#define rsz(...) resize(__VA_ARGS__)
#define psh(...) push_back(__VA_ARGS__)
#define emp(...) emplace_back(__VA_ARGS__)
#define prt(...) print(cout, __VA_ARGS__)
#define dprt(...) dbg(print(cerr,__VA_ARGS__))
#define dmp(...) dprt(#__VA_ARGS__, '=', __VA_ARGS__)
using namespace std;using ll=long long;
template<typename t>using V=vector<t>;
template<typename t>void print(ostream& os, const t& a){os<<a<<'\n';}
template<typename t, typename... A>void print
(ostream& os, const t& a, A&&... b){os<<a<<' ';print(os, b...);}
int n;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
V< V< bool > > rt(10, V< bool >(n));
V< V< bool > > tb(10, V< bool >(n));
for (int i = 9; i >= 0; --i)
{
string s; cin >> s;
for (int k = 0; k < n; ++k)
tb[i][k] = s[k] == '.';
}
queue< pair< int, int > > Q;
rt[0][0] = true;
Q.push({0, 0});
while (!Q.empty())
{
auto p = Q.front(); Q.pop();
// dprt(p.first, p.second);
if (p.second == n - 1)
continue;
if (p.first > 0 and rt[p.first - 1][p.second + 1] == false and
tb[p.first - 1][p.second + 1] == true)
{
rt[p.first - 1][p.second + 1] = true;
Q.push({p.first - 1, p.second + 1});
}
if (p.first < 9 and rt[p.first + 1][p.second + 1] == false and
tb[p.first + 1][p.second + 1] == true)
{
rt[p.first + 1][p.second + 1] = true;
Q.push({p.first + 1, p.second + 1});
}
if ((p.first == 0 or p.first == 9)
and rt[p.first][p.second + 1] == false and
tb[p.first][p.second + 1] == true)
{
rt[p.first][p.second + 1] = true;
Q.push({p.first, p.second + 1});
}
}
dbg(
for (int i = 9; i >= 0; --i)
{
for (int k = 0; k < n; ++k)
cerr << (rt[i][k]);
cerr << '\n';
}
);
int x = 0, y = n - 1;
while (rt[x][y] == false)
++x;
dmp(x, y);
V< pair< int, int > > ph;
ph.psh({x, y});
while (x != 0 or y != 0)
{
if (x > 0 and rt[x - 1][y - 1])
{
ph.psh({x - 1, y - 1});
--x, --y;
}
else if (x < 9 and rt[x + 1][y - 1])
{
ph.psh({x + 1, y - 1});
++x, --y;
}
else if ((x == 0 or x == 9) and rt[x][y - 1])
{
ph.psh({x, y - 1});
--y;
}
}
reverse(all(ph));
dbg(
for (auto& p : ph)
dprt(p.first, p.second);
);
V< pair< int, int > > odp;
for (int i = 0; i < ph.size(); ++i)
{
if (i < ph.size() - 1 and (ph[i].first < ph[i + 1].first or
(ph[i].first == 9 and ph[i + 1].first == 9)))
{
int pt = i + 1;
while (pt < ph.size() - 1 and
(ph[pt].first < ph[pt + 1].first or(ph[pt].first == 9 and
ph[pt + 1].first == 9)))
++pt;
odp.psh({i, pt - i});
i = pt;
}
}
prt(odp.size());
for (auto& p : odp)
prt(p.first, p.second);
}
Compilation message
jetpack.cpp: In function 'int main()':
jetpack.cpp:106:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ph.size(); ++i)
^
jetpack.cpp:108:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i < ph.size() - 1 and (ph[i].first < ph[i + 1].first or
^
jetpack.cpp:112:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (pt < ph.size() - 1 and
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
452 KB |
Output is correct |
| 4 |
Correct |
2 ms |
508 KB |
Output is correct |
| 5 |
Correct |
3 ms |
648 KB |
Output is correct |
| 6 |
Correct |
4 ms |
804 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1400 KB |
Output is correct |
| 8 |
Correct |
17 ms |
2208 KB |
Output is correct |
| 9 |
Correct |
23 ms |
3432 KB |
Output is correct |
| 10 |
Correct |
26 ms |
4756 KB |
Output is correct |
