Cod sursa(job #2128255)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 11 februarie 2018 16:27:34
Problema Castel Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>
#define MAXN 150

int n, m, k;
int v[1 + MAXN][1 + MAXN];
bool seen[1 + MAXN][1 + MAXN];
bool good[1 + MAXN * MAXN];
std::stack <int> key;
std::queue <std::pair<int, int>> q;
std::vector <std::pair<int, int>> V[1 + MAXN * MAXN];
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int main(){
    FILE*fi,*fo;
    fi = fopen("castel.in","r");
    fo = fopen("castel.out","w");

    fscanf(fi,"%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) fscanf(fi,"%d", &v[i][j]);

    int l, c;
    l = 1 + (k - 1) / m;
    c = 1 + (k - 1) % m;
    key.push(0);
    V[0].push_back({l, c});
    while(!key.empty()){
        int curr = key.top();
        key.pop();
        for(auto y: V[curr]) q.push(y), seen[y.first][y.second] = 1;
        good[curr] = 1;
        while(!q.empty()){
            std::pair <int, int> a = q.front(); q.pop();
            int l = a.first, c = a.second;
            key.push((l - 1) * m + c);
            for(int k = 0; k < 4; k++){
                int nl = l + dir[k][0], nc = c + dir[k][1];
                if(1 <= nl && nl <= n && 1 <= nc && nc <= m && !seen[nl][nc]){
                    if(good[v[nl][nc]]){
                        seen[nl][nc] = 1;
                        q.push({nl, nc});
                    }
                    else V[v[nl][nc]].push_back({nl, nc});
                }
            }
        }
    }
    int con = 0;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) con += seen[i][j];
    fprintf(fo,"%d", con);

    return 0;
}