Cod sursa(job #1606653)

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

using namespace std;

struct Camera{
    int numar, cheie, cheiVizita;
    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 main()
{
    FILE *fin = fopen("castel.in", "r");
    FILE *fout = fopen("castel.out", "w");

    int n, m, indStart, accesibil, 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();

        // cout << x << " " << y << "\n";

        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 || nrChei > mat[cx][cy].cheiVizita )&& areCheia[mat[cx][cy].cheie]){
                coada.push(make_pair(cx, cy));
                if(!areCheia[mat[cx][cy].numar]){
                    areCheia[mat[cx][cy].numar] = true;
                    nrChei++;
                }
                if(!mat[cx][cy].aFostVizitata){
                    mat[cx][cy].aFostVizitata = true;
                    accesibil++;
                }
                mat[cx][cy].cheiVizita = nrChei;
                // cout << "am luat cheia " << mat[cx][cy].numar << "\n";
            }
        }
    }

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