Cod sursa(job #1331796)

Utilizator diana97Diana Ghinea diana97 Data 1 februarie 2015 11:10:50
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 150, MMAX = 150;

int n, m, k;
int dx[4] = {-1,  0,  1,  0};
int dy[4] = { 0,  1,  0, -1};
queue <int> Q;
vector <int> urm[NMAX * MMAX];
int cheie[NMAX + 1][MMAX + 1];
bool inQ[NMAX * MMAX + 1];


void citeste() {
    f >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            f >> cheie[i][j];
}

inline pair <int, int> pozitie(int nr) {
    int x, y;
    x = nr / m + 1;
    y = nr % m;
    if (y == 0) x--, y += m;
    pair <int, int> p;
    p.first = x;
    p.second = y;
    return p;
}

inline int cod(int x, int y) {
    return (x - 1) * m + y;
}

inline bool interior(int x, int y) {
    if (x < 1 || y < 1) return false;
    if (x > n || y > m) return false;
    return true;
}

void intra(int camera) {
    int x, y, l, c, a, b;

    l = urm[camera].size();
    pair <int, int> p = pozitie(camera);
    x = p.first, y = p.second;

    for (int i = 0; i < l; i++) {
        c = urm[camera][i];
        if (!inQ[c]) {Q.push(c); inQ[c] = true;}
    }
    urm[camera].clear();

    for (int i = 0; i < 4; i++) {
        a = x + dx[i];
        b = y + dy[i];
        if (!interior(a, b)) continue;
        c = cod(a, b);
        if (!inQ[c]) {
            if (inQ[cheie[a][b]]) {Q.push(c); inQ[c] = true;}
            else urm[cheie[a][b]].push_back(c);
        }
    }

}

void rezolva() {
    Q.push(k);
    inQ[k] = true;
    while(!Q.empty()) {
        intra(Q.front());
        Q.pop();
    }
    int sol = 0;
    for (int i = 1; i <= n * m; i++)
        if (inQ[i]) sol++;
    g << sol << '\n';
}

int main() {
    citeste();
    rezolva();
}