Cod sursa(job #1631425)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 5 martie 2016 15:56:52
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <queue>
#define MAXN 150
using namespace std;

int key[MAXN + 1][MAXN + 1], nrkeys[MAXN + 1][MAXN + 1];
bool inQ[MAXN + 1][MAXN + 1];
bool iskey[(MAXN * MAXN) + 1];
int linie[4] = {-1, 0, 1, 0}, coloana[4] = {0, 1, 0, -1};
struct pos{
    int lin, col;
};
typedef queue <pos> coada;
coada Q;
int m, n, k;

int main () {
    ifstream cin("castel.in");
    ofstream cout("castel.out");

    cin >> m >> n >> k;

    for (int i = 1 ; i <= m ; ++i)
        for (int j = 1 ; j <= n ; ++j)
            cin >> key[i][j];

    pos pk, ins, x;
    pk.lin = k / n;
    pk.col = k % n;

    if (pk.col > 0)
        ++pk.lin;
    else
        pk.col = n;

    iskey[k] = true;
    int disp = 1;
    nrkeys[pk.lin][pk.col] = 1;
    Q.push(pk);
    inQ[pk.lin][pk.col] = true;

    while (!Q.empty()) {
        x = Q.front();
        Q.pop();
        inQ[x.lin][x.col] = false;

        for (int i = 0 ; i < 4 ; ++i) {
            int l = x.lin + linie[i], c = x.col + coloana[i];
            if (l > 0 && l <= m && c > 0 && c <= n && iskey[key[l][c]]) {
                int cel = (n * (l - 1)) + c;
                if (!iskey[cel]) {
                    ++disp;
                    iskey[cel] = true;
                }

                if (disp > nrkeys[l][c]) {
                    nrkeys[l][c] = disp;
                    if (!inQ[l][c]) {
                        ins.lin = l;
                        ins.col = c;
                        Q.push(ins);
                        inQ[l][c] = true;
                    }
                }
            }
        }
    }

    int sol = 0;
    for (int i = 1 ; i <= m ; ++i)
        for (int j = 1 ; j <= n ; ++j)
            if (nrkeys[i][j] > 0)
                ++sol;

    cout << sol << "\n";
    return 0;
}