Cod sursa(job #1244416)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 17 octombrie 2014 13:17:39
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <fstream>
#include <vector>
#define NMax 151
using namespace std;
ifstream f("castel.in");
ofstream g("castel.out");
int m, n, k, mat[NMax][NMax], viz[NMax][NMax], qu[2][NMax*NMax], i, j, p, u, x, y, l, c, nrc=1, chei[NMax*NMax], oc[NMax][NMax], ok;
vector<pair<int,int> > nedes[NMax*NMax];
const int dx[]={0, -1, 0, 1, 0}, dy[]={0, 0, 1, 0, -1};
int main() {
    f>>m>>n>>k;
    for (i=1; i<=m; i++)
        for (j=1; j<=n; j++)
            f>>mat[i][j];
    if (k%n==0)
        x=k/n;
    else
        x=k/n+1;
    y=k-(x-1)*n;
    viz[x][y]=1;
    p=u=1;
    qu[0][p]=x;
    qu[1][p]=y;
    chei[(x-1)*n+y]=mat[x][y];
    while (p<=u) {
        int x=(qu[0][p]-1)*n+qu[1][p];
        if (!nedes[x].empty()) {
            for (i=0; i<nedes[x].size(); i++) {
                chei[(nedes[x][i].first-1) * n + nedes[x][i].second ]=1;
                u++;
                qu[0][u]=nedes[x][i].first;
                qu[1][u]=nedes[x][i].second;
                nrc++;
            }
            nedes[x].clear();
        }
        for (i=1; i<=4; i++) {
            l=dx[i]+qu[0][p];
            c=dy[i]+qu[1][p];
            if (viz[l][c]==0 && l>=1 && l<=m && c>=1 && c<=n) {
                if (chei[mat[l][c]]) {
                    viz[l][c]=1;
                    u++;
                    qu[0][u]=l;
                    qu[1][u]=c;
                    if (!oc[l][c])
                        nrc++;
                    int codif=(l-1)*n+c;
                    chei[codif]=1;
                    if (!nedes[codif].empty()) {
                        for (i=0; i<nedes[codif].size(); i++) {
                            chei[(nedes[codif][i].first-1) * n + nedes[codif][i].second ]=1;
                            u++;
                            qu[0][u]=nedes[codif][i].first;
                            qu[1][u]=nedes[codif][i].second;
                            nrc++;
                        }
                        nedes[codif].clear();
                    }
                }
                else
                    if (!oc[l][c]) {
                        nedes[mat[l][c]].push_back(make_pair(l, c));
                        oc[l][c]=1;
                    }
            }
        }
        p++;
    }
    g<<nrc;
    return 0;
}