Cod sursa(job #1749198)

Utilizator tudortarniceruTudor Tarniceru tudortarniceru Data 28 august 2016 01:27:45
Problema Castel Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 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;
}
void 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];
        for (int q = 0; q < vx[encod(x, y)].size(); ++q) {
            dr++;
            int ax = vx[encod(x, y)][q];
            int bx = vy[encod(x, y)][q];
            av[ax][bx] = 1;
            c[1][dr] = ax;
            c[2][dr] = bx;
            vx[encod(x, y)].clear();
            vy[encod(x, y)].clear();
        }
        //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;
                    if (ch[encod(x, y)] == 0) {
                        ch[encod(x, y)] = 1;
                    }
                }
                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;
}