Cod sursa(job #2164935)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 13 martie 2018 10:29:58
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 150;

int keys[MAXN + 1][MAXN + 1];

vector < pair <char, char> > pos[MAXN * MAXN + 1];

pair <char, char> q[MAXN * MAXN + 1];
bool vis[MAXN + 1][MAXN + 1];
bool ok[MAXN * MAXN + 1];

char dl[] = {-1, 0, 1, 0}, dc[] = {0, -1, 0, 1};
int n, m, b, e;

inline int get(int l, int c) {
    return (l - 1) * m + c;
}

inline void check(int id) {
    for(auto it : pos[id]) {
        int l = it.first, c = it.second;
        if(vis[l][c])
            continue;
        for(int i = 0; i < 4; i++) {
            int lin = l + dl[i], col = c + dc[i];
            if(lin > 0 && col > 0 && lin <= n && col <= m && vis[lin][col]) {
                q[e++] = {l, c};
                vis[l][c] = 1;
                ok[get(l, c)] = 1;
            }
        }
    }
}

int main() {
    FILE *fi, *fout;
    int i, j, k;
    fi = fopen("castel.in" ,"r");
    fout = fopen("castel.out" ,"w");
    fscanf(fi,"%d %d %d " ,&n,&m,&k);
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            fscanf(fi,"%d " ,&keys[i][j]);
            pos[keys[i][j]].push_back({i, j});
        }
    }
    int c = (k - 1) % m + 1;
    int l = (k - c) / m + 1;
    q[e++] = {l, c};
    vis[l][c] = 1;
    ok[get(l, c)] = 1;
    while(b < e) {
        l = q[b].first;
        c = q[b].second;
        b++;
        for(int i = 0; i < 4; i++) {
            int lin = l + dl[i], col = c + dc[i];
            if(lin > 0 && col > 0 && lin <= n && col <= m && vis[lin][col] == 0 && ok[keys[lin][col]]) {
                vis[lin][col] = 1;
                ok[get(lin, col)] = 1;
                q[e++] = {lin, col};
            }
        }
        check(keys[l][c]);
    }
    fprintf(fout,"%d" ,e);
    fclose(fi);
    fclose(fout);
    return 0;
}