Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
3.0 kB
1
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> pii;
int N;
char grid[11][100005];
int press[11][100005][2];
pii last[11][100005][2];
stack <pii> path;
vector <pii> ans;
int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N;
    for (int i=9; i>=0; i--){
        for (int j=0; j<N; j++){
            cin >> grid[i][j];
        }
    }
    memset(press, INF, sizeof(press));
    press[0][0][0] = 0;
    for (int j=1; j<N; j++){
        if (grid[0][j] == '.') {
            if (press[0][j - 1][0] < press[1][j - 1][0]) {
                press[0][j][0] = press[0][j - 1][0];
                last[0][j][0] = {0, 0};
            } else {
                press[0][j][0] = press[1][j - 1][0];
                last[0][j][0] = {1, 0};
            }
        }
        if (grid[9][j] == '.'){
            if (press[9][j-1][1] < press[8][j-1][1]){
                press[9][j][1] = press[9][j-1][1];
                last[9][j][1] = {9, 1};
            } else {
                press[9][j][1] = press[8][j-1][1];
                last[9][j][1] = {8, 1};
            }
        }
        for (int i=1; i<9; i++){
            if (grid[i][j] != '.') continue;
            if (press[i-1][j-1][0]+1 < press[i-1][j-1][1]){
                press[i][j][1] = press[i-1][j-1][0]+1;
                last[i][j][1] = {i-1, 0};
            } else {
                press[i][j][1] = press[i-1][j-1][1];
                last[i][j][1] = {i-1, 1};
            }
            if (press[i+1][j-1][0] < press[i+1][j-1][1]){
                press[i][j][0] = press[i+1][j-1][0];
                last[i][j][0] = {i+1, 0};
            } else {
                press[i][j][0] = press[i+1][j-1][1];
                last[i][j][0] = {i+1, 1};
            }
        }
    }
    int best = INF, loc = 0, state = 0;
    for (int i=0; i<9; i++){
        for (int k=0; k<=1; k++){
            if (press[i][N-1][k] < best){
                best = press[i][N-1][k];
                loc = i; state = k;
            }
        }
    }
    path.push({-1, N});
    path.push({loc, N-1});
    for (int i=N-1; i>=1; i--){
        int a = path.top().first, b = path.top().second;
        path.push({last[a][i][state].first, i-1});
        state = last[a][i][state].second;
    }
    int height = 0, start = 0;
    bool push = false;
    path.pop();
    while (!path.empty()){
        pii a = path.top();
        if ((a.first == 9 || a.first > height) && !push){
            push = true;
            start = a.second-1;
        }
        else if (a.first < height && push){
            push = false;
            ans.push_back({start, a.second - start - 1});
        }
        height = a.first;
        path.pop();
    }
    cout << (int)ans.size() << "\n";
    for (pii e: ans){
        cout << e.first << " " << e.second << "\n";
    }
    return 0;
}