Cod sursa(job #2128289)

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

#define BUF_SIZE 1 << 14
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline int nextnum(){
    int a = 0;
    char c = nextch();
    while(!isdigit(c))
        c = nextch();
    while(isdigit(c)){
        a = a * 10 + c - '0';
        c = nextch();
    }
    return a;
}

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

    n = nextnum(), m = nextnum(), k = nextnum();
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) v[i][j] = nextnum();

    int l, c;
    l = 1 + (k - 1) / m;
    c = 1 + (k - 1) % m;
    key[++last] = 0;
    V[0].push_back({l, c});
    while(last != 0){
        int curr = key[last--];
        p = u = 0;
        for(auto y: V[curr]) q[u++] = y, seen[y.first][y.second] = ok[y.first][y.second] = 1;
        good[curr] = 1;
        while(p != u){
            std::pair <int, int> a = q[p++];
            int l = a.first, c = a.second;
            key[++last] = (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]){
                    seen[nl][nc] = 1;
                    if(good[v[nl][nc]]){
                        ok[nl][nc] = 1;
                        q[u++] = {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 += ok[i][j];
    fprintf(fo,"%d", con);

    return 0;
}