Cod sursa(job #2763575)

Utilizator DragosC1Dragos DragosC1 Data 15 iulie 2021 12:05:11
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

int cstart, n, m;
int a[151][151];
int rez;

void read() {
    int i, j;
    ifstream f("castel.in");
    f >> n >> m >> cstart;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            f >> a[i][j];
    f.close();
}

queue<int> Q;

const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};

int viz[150 * 150 + 1];
vector<int> list[150 * 150 + 1]; 
int cheie[150 * 150 + 1];

bool inside(int i, int j) {
    if (i >= 1 && j >= 1 && i <= n && j <= m)
        return 1;
    return 0;
}

void parcurg(int start) {
    int i, j, inou, jnou, k, x;
    Q.push(start);
    viz[start] = 1;
    while (!Q.empty()) {
        x = Q.front();
        Q.pop();
        i = (x - 1) / m + 1, j = (x - 1) % m + 1;
        cheie[x] = 1;
        for (k = 0; k < 4; k++) {
            inou = i + di[k], jnou = j + dj[k];
            if (inside(inou, jnou) && viz[(inou - 1) * m + jnou] == 0) {
                if (cheie[a[inou][jnou]]) {
                    viz[(inou - 1) * m + jnou] = 1;
                    Q.push((inou - 1) * m + jnou);
                }
                else 
                    list[a[inou][jnou]].push_back((inou - 1) * m + jnou);
            }
        }
        for (k = 0; k < list[x].size(); k++) 
            if (!viz[list[x][k]]) {
                viz[list[x][k]] = 1;
                Q.push(list[x][k]);
            }
    }
}

void solve() {
    parcurg(cstart);
    int i, j;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            rez += viz[(i - 1) * m + j];
}

void output() {
    ofstream g("castel.out");
    g << rez;
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}