Cod sursa(job #1749193)

Utilizator tudortarniceruTudor Tarniceru tudortarniceru Data 28 august 2016 01:04:57
Problema Castel Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("castel.in");
ofstream fout("castel.out");
const int MAXN = 155;
int n, m;
int v[MAXN][MAXN];
bool av[MAXN][MAXN];
bool ch[MAXN * MAXN];
int c[3][MAXN * MAXN];
vector<int> vx[MAXN * MAXN], vy[MAXN * MAXN];
int d1[5], d2[5];
struct coord {
    int x;
    int y;
} cv;
coord decod (int x) {
    coord q;
    q.x = x / m + 1;
    q.y = x % m;
    if (x == 0) {
        q.y = m;
        q.x--;
    }
    return q;
}
int encod (int x, int y) {
    return (x - 1) * m + y;
}
int border() {
    for (int i = 0; i <= n + 1; ++i) {
        av[i][0] = 1;
        av[i][m + 1] = 1;
    }
    for (int i = 0; i <= m + 1; ++i) {
        av[0][i] = 1;
        av[n + 1][i] = 1;
    }
}
int main() {
    d1[1] = -1; d1[2] = 0; d1[3] = 1; d1[4] = 0;
    d2[1] = 0; d2[2] = 1; d2[3] = 0; d2[4] = -1;
    fin >> n >> m;
    border();
    int l;
    fin >> l;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            fin >> v[i][j];
        }
    }
    int st = 1, dr = 1;
    cv = decod(l);
    c[1][st] = cv.x;
    c[2][st] = cv.y;
    av[cv.x][cv.y] = 1;
    ch[l] = 1;
    while (st <= dr) {
        int x = c[1][st];
        int y = c[2][st];
        //fout << x << ' ' << y << '\n';
        for (int k = 1; k <= 4; ++k) {
            int a = x + d1[k];
            int b = y + d2[k];
            if (av[a][b] == 0) {
                //fout << a << ' ' << b << '\n';
                if (ch[v[a][b]] == 1) {
                    dr++;
                    av[a][b] = 1;
                    c[1][dr] = a;
                    c[2][dr] = b;
                    ch[encod(a, b)] = 1;
                    for (int q = 0; q < vx[v[a][b]].size(); ++q) {
                        int ax = vx[v[a][b]][q];
                        int bx = vy[v[a][b]][q];
                        dr++;
                        av[ax][bx] = 1;
                        c[1][dr] = ax;
                        c[2][dr] = bx;
                    }
                }
                else {
                    vx[v[a][b]].push_back(a);
                    vy[v[a][b]].push_back(b);
                }
            }
        }
        st++;
    }
    int sol = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            sol += av[i][j];
        }
    }
    fout << sol;
    fout.close();
    return 0;
}