tunel2

/**
 * Diana Ghinea
 * iterativ + matrice N * M
 * O(M) timp
 * O(N * M) memorie suplimentara
 */

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("tunel2.in");
ofstream g("tunel2.out");

const int NMAX = 1000;
const int MMAX = 20000;

const int SUS = 0;
const int JOS = 1;
const int STANGA = 2;
const int DREAPTA = 3;

int c, n, m, x;

bool pasaj_in_jos[NMAX + 2][MMAX + 2];

void citeste() {
    f >> c;
    f >> n >> m >> x;

    for (int i = 1; i < n; i++) {
        int p;
        f >> p;
        for (int j = 1; j <= p; j++) {
            int poz;
            f >> poz;
            pasaj_in_jos[i][poz] = true;
        }
    }
}

inline bool am_pasaj_in_jos(int i, int j) {
    return pasaj_in_jos[i][j];
}

inline bool am_pasaj_in_sus(int i, int j) {
    return pasaj_in_jos[i - 1][j];
}

void c1() {
    int i = x, j = 1;
    int vin_din = STANGA;

    while (j <= m && !(i == n && j == m)) {
        if (vin_din == STANGA) {
            if (am_pasaj_in_sus(i, j)) {
                i--;
                vin_din = JOS;
                continue;
            }
            if (am_pasaj_in_jos(i, j)) {
                i++;
                vin_din = SUS;
                continue;
            }
        }
        j++;
        vin_din = STANGA;
    }

    g << i << '\n';
}

int traseu_c2(int i, int j, int vin_din, int pasaje) {
    while (j > 0) {
        if (vin_din == DREAPTA) {
            if (am_pasaj_in_sus(i, j)) {
                i--;
                vin_din = JOS;
                pasaje++;
                continue;
            }
            if (am_pasaj_in_jos(i, j)) {
                i++;
                vin_din = SUS;
                pasaje++;
                continue;
            }
        }
        j--;
        vin_din = DREAPTA;
    }

    return m + 2 * pasaje;
}

void c2() {
    int lungime_minima = traseu_c2(n, m - 1, DREAPTA, 0);
    if (am_pasaj_in_sus(n, m))
        lungime_minima = min(lungime_minima, traseu_c2(n - 1, m, JOS, 1));
    g << lungime_minima << '\n';
}

int main() {
    citeste();

    if (c == 1) c1();
    else c2();
    return 0;
}