Cod sursa(job #1606693)

Utilizator preda.andreiPreda Andrei preda.andrei Data 20 februarie 2016 14:24:16
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

struct Camera{
    int numar, cheie;
    bool aFostVizitata;
};

const short int modLin[4] = {-1, 0, 1, 0};
const short int modCol[4] = {0, 1, 0, -1};

Camera mat[151][151];
bool areCheia[22510];
queue< pair<short int, short int> > coada;
int inAsteptare[22510][101];

int accesibil, n, m;

void deschideCamera(int x, int y);

int main()
{
    FILE *fin = fopen("castel.in", "r");
    FILE *fout = fopen("castel.out", "w");

    int indStart, x, y, cx, cy, nrChei;

    fscanf(fin, "%d%d%d", &n, &m, &indStart);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            fscanf(fin, "%d", &mat[i][j].cheie);
            mat[i][j].numar = (i - 1) * m + j;
            if(mat[i][j].numar == indStart){
                coada.push(make_pair(i, j));
                mat[i][j].aFostVizitata = true;
                areCheia[mat[i][j].numar] = true;
                accesibil = 1;
            }
        }
    }

    nrChei = 1;
    while(!coada.empty()){
        x = coada.front().first;
        y = coada.front().second;
        coada.pop();

        for(int i = 0; i < 4; ++i){
            cx = x + modLin[i];
            cy = y + modCol[i];
            if(cx >= 1 && cx <= n && cy >= 1 && cy <= m && !mat[cx][cy].aFostVizitata){
                if(areCheia[mat[cx][cy].cheie])
                    deschideCamera(cx, cy);
                else inAsteptare[mat[cx][cy].cheie][++inAsteptare[mat[cx][cy].cheie][0]] = mat[cx][cy].numar;
            }
        }
    }

    fprintf(fout, "%d", accesibil);
    return 0;
}

void deschideCamera(int x, int y){
    if(mat[x][y].aFostVizitata)
        return;

    int lin, col, cheiaNoua;

    areCheia[mat[x][y].numar] = true;
    accesibil++;
    mat[x][y].aFostVizitata = true;
    coada.push(make_pair(x, y));

    cheiaNoua = mat[x][y].numar;
    while(inAsteptare[cheiaNoua][0] > 0){
        lin = (inAsteptare[cheiaNoua][inAsteptare[cheiaNoua][0]] - 1) / m + 1;
        col = inAsteptare[cheiaNoua][inAsteptare[cheiaNoua][0]] % m;
        if(col == 0)
            col = m;

        inAsteptare[cheiaNoua][0]--;
        deschideCamera(lin, col);
    }
}