#include <bits/stdc++.h>
#define endl "\n"
using namespace std ;
typedef long long ll;
typedef long double ld ;
const int N=2e7;
const ll inf=1e18 ;
const ll mod = 1e9 + 7 ;
ll mypower(ll x, ll y){
if(y == 0) return 1 ;
if(y == 1) return x ;
ll ret = mypower(x , y / 2);
ret = (ret * ret) % mod;
if(y % 2) ret = ( ret * x ) % mod ;
return ret ;
}
ll n ;
char a[20][100009] ;
bool is2[20][100009] , is[20][100009] ;
vector < pair < ll , ll > > ans ;
ll la ;
void sol(ll i , ll j , ll ti , ll len , ll iss){
a[i][j] = '*' ;
if(iss == 0){
if(j == n - 1){
return ;
}
if(is2[i][j] && a[i - 1][j + 1] != 'X'){
la = ti ;
sol(i - 1 , j + 1 , ti + 1 , len + 1 , 1) ;
}
else{
sol(i , j + 1 , ti + 1 , len , 0) ;
}
}
else if(iss == 1){
if(j == n - 1){
ans.push_back({la , len}) ;
return ;
}
if(is[i][j] && a[i + 1][j + 1] != 'X'){
ans.push_back({la , len}) ;
la = 0 ;
sol(i + 1 , j + 1 , ti + 1 , 0 , 2) ;
}
else if(i != 0 && a[i - 1][j + 1] != 'X'){
sol(i - 1 , j + 1 , ti + 1 , len + 1 , 1) ;
}
else{
sol(i , j + 1 , ti + 1 , len + 1 ,1) ;
}
}
else{
if(j == n - 1){
return ;
}
if(is2[i][j] && a[i - 1][j + 1] != 'X'){
la = ti ;
sol(i - 1 , j + 1 , ti + 1 , len + 1 , 1) ;
}
else if(i != 9 && a[i + 1][j + 1] !='X'){
sol(i + 1 ,j + 1 , ti + 1 , 0 , 2) ;
}
else if(i == 9 && a[i][j + 1] != 'X'){
sol(i , j + 1 , ti + 1 , 0 , 2) ;
}
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n ;
for(int j = 0 ; j < 10 ; j++){
for(int i = 0 ; i < n ; i++){
cin >> a[j][i] ;
}
}
is[0][n - 1] = is[9][n - 1] = 1 ;
is2[0][n - 1] = is2[9][n - 1] = 1 ;
for(int i = n - 1 ; i >= 0 ; i--){
is2[0][i] |= is2[0][i + 1] ;
is[0][i] |= is[0][i + 1] ;
is2[9][i] |= is2[9][i + 1] ;
is[9][i] |= is[9][i + 1] ;
}
for(int j = n - 1 ; j >= 0 ; j--){
for(int i = 9 ; i >= 0 ; i--){
if(j == n - 1 && a[i][j] == '.'){
is[i][j] = is2[i][j] = 1 ;
continue ;
}
if(a[i][j] == 'X'){
continue ;
}
is[i][j] = is[i + 1][j + 1] | is2[i + 1][j + 1] ;
is2[i][j] = is2[i - 1][j + 1] | is[i - 1][j + 1] ;
}
}
ll x = 9 , y = 0 , ti = 0 , len = 0 ;
sol(x , y , ti , len , 0) ;
cout << ans.size() << endl ;
for(auto p : ans){
cout << p.first << " " << p.second << endl ;
}
// for(int i = 0 ; i < 10 ;i++){
// for(int j = 0 ; j< n ;j++){
// cout << a[i][j] ;
// }
// cout << endl ;
// }
// cout << a[9][0] << endl ;
return 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Crashed with an obstacle |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Crashed with an obstacle |
| 4 |
Incorrect |
1 ms |
464 KB |
Crashed with an obstacle |
| 5 |
Incorrect |
1 ms |
596 KB |
Crashed with an obstacle |
| 6 |
Incorrect |
2 ms |
596 KB |
Crashed with an obstacle |
| 7 |
Incorrect |
4 ms |
1108 KB |
Crashed with an obstacle |
| 8 |
Incorrect |
9 ms |
2216 KB |
Crashed with an obstacle |
| 9 |
Incorrect |
14 ms |
3156 KB |
Crashed with an obstacle |
| 10 |
Incorrect |
20 ms |
4180 KB |
Crashed with an obstacle |
