#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
typedef pair<int, int> pi;
typedef long long int lint;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
int n;
char a[13][maxn];
queue<int> qx, qy;
int memo[13][maxn];
pi put[13][maxn];
int mini = inf, indeks = -1;
vector<pi> potezi;
bool ok(int t1, int t2) {
if(t1 < 0 or t2 < 0 or t1 >= 10 or t2 >= n) return 0;
if(a[t1][t2] != '.' or memo[t1][t2] != -1) return 0;
return 1;
}
int main ()
{
ios::sync_with_stdio(0);
cin >> n;
for(int i = 0; i < 10; ++i)
for(int j = 0; j < n; ++j)
cin >> a[i][j];
memset(memo, -1, sizeof memo);
qx.push(9); qy.push(0);
memo[9][0] = 0;
while(!qx.empty()) {
int x = qx.front();
int y = qy.front();
qx.pop(); qy.pop();
if(ok(x + 1, y + 1)) {
memo[x + 1][y + 1] = memo[x][y] + 1;
qx.push(x + 1); qy.push(y + 1);
put[x + 1][y + 1] = mp(x, y);
}
if(ok(x - 1, y + 1)) {
memo[x - 1][y + 1] = memo[x][y] + 1;
qx.push(x - 1); qy.push(y + 1);
put[x - 1][y + 1] = mp(x, y);
}
if((x == 0 or x == 9) and ok(x, y + 1)) {
memo[x][y + 1] = memo[x][y] + 1;
qx.push(x); qy.push(y + 1);
put[x][y + 1] = mp(x, y);
}
}
/*
for(int i = 0; i < 10; ++i) {
for(int j = 0; j < n; ++j)
cout << memo[i][j] << " ";
cout << endl;
}
*/
for(int i = 0; i < 10; ++i)
if(memo[i][n - 1] < mini and memo[i][n - 1] != -1)
mini = memo[i][n - 1], indeks = i;
int x = indeks, y = n - 1;
int sek = 0;
// int count = 0;
while(memo[indeks][n - 1]--) {
int exx = put[x][y].ff;
int exy = put[x][y].ss;
a[exx][exy] = '*';
if(exx - 1 == x and exy + 1 == y or (exx == x and x == 0))
++sek;
else if(sek) {
potezi.pb(mp(memo[indeks][n - 1], sek));
sek = 0;
// ++count;
}
x = exx, y = exy;
}
/*
for(int i = 0; i < 10; ++i) {
for(int j = 0; j < n; ++j)
cout << a[i][j];
cout << endl;
}
*/
cout << potezi.size() << endl;
reverse(potezi.begin(), potezi.end());
for(int i = 0; i < potezi.size(); ++i)
cout << potezi[i].first << " " << potezi[i].second << endl;
return 0;
}
//written and directed by pcelicamaja
Compilation message
jetpack.cpp: In function 'int main()':
jetpack.cpp:81:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if(exx - 1 == x and exy + 1 == y or (exx == x and x == 0))
~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
jetpack.cpp:100:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < potezi.size(); ++i)
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5504 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5504 KB |
Crashed with an obstacle |
| 3 |
Incorrect |
6 ms |
5504 KB |
Crashed with an obstacle |
| 4 |
Incorrect |
7 ms |
5632 KB |
Crashed with an obstacle |
| 5 |
Incorrect |
13 ms |
5888 KB |
Crashed with an obstacle |
| 6 |
Incorrect |
14 ms |
6144 KB |
Crashed with an obstacle |
| 7 |
Incorrect |
23 ms |
7424 KB |
Crashed with an obstacle |
| 8 |
Incorrect |
49 ms |
10108 KB |
Crashed with an obstacle |
| 9 |
Incorrect |
72 ms |
12404 KB |
Crashed with an obstacle |
| 10 |
Incorrect |
96 ms |
14968 KB |
Crashed with an obstacle |
