Cod sursa(job #1563883)

Utilizator lflorin29Florin Laiu lflorin29 Data 6 ianuarie 2016 23:52:05
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 157;

int N, M, start_room;
int A[MAX_N * MAX_N], cod[MAX_N][MAX_N];
vector<int>vec[MAX_N * MAX_N];
vector<int>vec2[MAX_N * MAX_N];

bool canuse(int x, int y) {
    return x > 0 && y > 0 && x<=N && y <=M;
}

const int vecX[] = {-1, 0, 1, 0};
const int vecY[] = {0, 1, 0, -1};

void Read() {
    ifstream fin("castel.in");
    fin >> N >> M >> start_room;
    for(int i=1; i <= N * M; ++i)
       fin >> A[i],vec2[A[i]].push_back(i);

    int tmp = 1;
    for(int i=1; i <= N; ++i)
        for(int j=1; j <= M; ++j)
           cod[i][j] = tmp++;
    tmp = 1;
    for(int i=1; i <= N; ++i)
        for(int j=1; j <= M; ++j) {
            for(int k=0; k < 4; ++k) {
                int ni = i + vecX[k], nj = j + vecY[k];
                if(canuse(ni, nj)) vec[tmp].push_back(cod[ni][nj]);
            }
            ++tmp;
        }
}

bool fols[MAX_N * MAX_N];
void Solve() {
    unordered_map<int, int>keys;
    keys[start_room] = 1;
    queue<int>q; q.push(start_room); fols[start_room] = 1;
    while(!q.empty()) {
         int act = q.front(); q.pop();
         for(int son : vec[act]) {
            int key_req = A[son];
            if(keys.find(key_req) != keys.end() && fols[son] == 0) {
                fols[son] ++;
                q.push(son);
                keys[son]=1;
            }
         }

         for(auto l =vec2[act].begin();l!=vec2[act].end();++l) {
            if(fols[*l]) continue;
            bool canHere = 0;
            for(int j : vec[*l]) {
             if(fols[j]) {canHere = 1; break;}
            }
            if(canHere){
                q.push(*l);
            fols[*l]=1;
            keys[*l]=1;
         }
    }
}
    int folst = 0;
    for(int i=1; i <= N*M; ++i)
       folst += fols[i] ;
    ofstream("castel.out") << folst;
}

int main() {
    Read();
    Solve();
    return 0;
}