#include<bits/stdc++.h>
using namespace std;
long long mod=1e9+7;
int n,dp[14][100005];
char gr[14][100005];
int f(int x,int y,int up)
{
if(y==n)return true;
if(gr[x][y]=='X')return false;
if(dp[x][y]!=-1)return dp[x][y];
int pos=false;
pos=max(pos,f(max(0,x-1),y+1,1));
pos=max(pos,f(min(9,x+1),y+1,0));
return dp[x][y]=pos;
}
vector<int>a,b;
void dfs(int x,int y,int up,int time)
{
if(y==n-1)
{
cout<<a.size()<<endl;
if(time!=0)b.push_back(time);
for(int i=0;i<a.size();i++)cout<<a[i]<<' '<<b[i]<<endl;
exit(0);
}
int nx=max(0,x-1),ny=y+1;
if(dp[nx][ny]==1)
{
if(up==1)dfs(nx,ny,1,time+1);
else
{
a.push_back(y);
dfs(nx,ny,1,time+1);
}
}
nx=min(9,x+1),ny=y+1;
if(dp[nx][ny]==1)
{
if(up==1)
{
b.push_back(time);
dfs(nx,ny,0,0);
}
else dfs(nx,ny,0,0);
}
}
int main()
{
memset(dp,-1,sizeof dp);
cin>>n;
for(int i=0;i<10;i++)
{
for(int j=0;j<n;j++)cin>>gr[i][j];
}
f(9,0,0);
dfs(9,0,0,0);
}
Compilation message
jetpack.cpp: In function 'void dfs(int, int, int, int)':
jetpack.cpp:23:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a.size();i++)cout<<a[i]<<' '<<b[i]<<endl;
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5884 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5880 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5880 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5880 KB |
Output is correct |
| 5 |
Correct |
14 ms |
6264 KB |
Output is correct |
| 6 |
Correct |
16 ms |
6392 KB |
Output is correct |
| 7 |
Correct |
34 ms |
7544 KB |
Output is correct |
| 8 |
Correct |
77 ms |
10104 KB |
Output is correct |
| 9 |
Correct |
112 ms |
12268 KB |
Output is correct |
| 10 |
Correct |
169 ms |
15068 KB |
Output is correct |
