#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN=1e5;
int n;
string g[10];
ar<int, 2> dp[mxN][10];
vector<bool> ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i=9; ~i; --i)
cin >> g[i];
memset(dp, -1, sizeof(dp));
dp[0][0]={};
for (int i=0; i+1<n; ++i) {
for (int j=0; j<10; ++j) {
if (dp[i][j][0]==-1)
continue;
if (j&&g[j-1][i+1]=='.')
dp[i+1][j-1]={j, 0};
else if (j==0&&g[j][i+1]=='.')
dp[i+1][j]={j, 0};
if (j+1<10&&g[j+1][i+1]=='.')
dp[i+1][j+1]={j, 1};
else if (j==9&&g[j][i+1]=='.')
dp[i+1][j]={j, 1};
}
}
int j=-1;
for (int i=0; i<10; ++i)
if (dp[n-1][i][0]^-1)
j=i;
assert(j^-1);
for (int i=n-1; i; --i) {
assert(dp[i][j][0]^-1);
ans.push_back(dp[i][j][1]);
j=dp[i][j][0];
}
reverse(ans.begin(), ans.end());
vector<ar<int, 2>> ans2;
for (int i=0; i<n-1; ++i) {
if (!ans[i])
continue;
for (j=i; j+1<n-1&&ans[j+1]; ++j);
ans2.push_back({i, j-i+1});
i=j;
}
cout << ans2.size() << "\n";
for (ar<int, 2> a : ans2)
cout << a[0] << " " << a[1] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8140 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8012 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8140 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8140 KB |
Output is correct |
| 5 |
Correct |
4 ms |
8220 KB |
Output is correct |
| 6 |
Correct |
5 ms |
8268 KB |
Output is correct |
| 7 |
Correct |
6 ms |
8524 KB |
Output is correct |
| 8 |
Correct |
9 ms |
9164 KB |
Output is correct |
| 9 |
Correct |
13 ms |
9804 KB |
Output is correct |
| 10 |
Correct |
16 ms |
10572 KB |
Output is correct |
