Cod sursa(job #1636952)

Utilizator vlad6001Pintilie Vlad vlad6001 Data 7 martie 2016 13:43:53
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.52 kb
#include <fstream>
using namespace std;

ifstream fin("castel.in");
ofstream fout("castel.out");

int matrice[160][160], coada[25000], linii, q, coloane, l, c, inceput, i, j, in, copie, sf, linie, coloana, x, iul, jul, val, cheie[23000], z, cate[23000], tine[23000][20];
int i_afis, j_afis, lin, col, minte;
int dir_i[] = {0, -1, 0, 1, 0};
int dir_j[] = {0, 0, 1, 0, -1};

int main()
{
    fin >> linii >> coloane >> inceput;
    cheie[inceput] = 1;
    for(i=1; i <= linii; i++)
    {
        for(j=1; j <= coloane; j++)
        fin >> matrice[i][j];
    }

    for(x=0; x <= linii+1; x++)
    {
        matrice[x][coloane+1] = -1;
        matrice[x][0] = -1;
    }
    for(x=0; x <= coloane+1; x++)
    {
        matrice[0][x] = -1;
        matrice[linii+1][x] = -1;
    }

    coada[1] = inceput;
    in = 1;
    sf = 1;

    while(in <= sf)
    {
        i = coada[in]/coloane+1;
        j = coada[in]%coloane;
        if(j == 0)
        {
            i--;
            j = coloane;
        }
        matrice[i][j] = -1;

        for(x=1; x <= 4; x++)
        {
            iul = i + dir_i[x];
            jul = j + dir_j[x];

            if(matrice[iul][jul] != -1)
            {
                val = matrice[iul][jul];
                if(cheie[val] == 1)
                {
                    sf++;
                    coada[sf] = (iul-1)*coloane + jul;
                    copie = coada[sf];
                    cheie[coada[sf]] = 1;
                    matrice[iul][jul] = -1;
                    for(z=1; z <= cate[copie]; z++)
                    {
                        minte = tine[copie][z];
                        lin = minte/coloane+1;
                        col = minte%coloane;
                        if(lin == 0)
                        {
                            lin--;
                            col = coloane;
                        }

                        if(matrice[lin][col] != -1)
                        {
                            sf++;
                            coada[sf] = tine[copie][z];
                            matrice[lin][col] = -1;
                            cheie[minte] = 1;
                            for(q=1; q <= cate[minte]; q++)
                            {
                                l = tine[minte][q]/coloane+1;
                                c = tine[minte][q]%coloane;
                                if(l == 0)
                                {
                                    l--;
                                    c = coloane;
                                }
                                if(matrice[l][c] != -1)
                                {
                                    sf++;
                                    coada[sf] = tine[tine[copie][z]][q];
                                    matrice[l][c] = -1;
                                    cheie[tine[copie][z]] = 1;
                                }
                            }
                        }
                    }
                }
                else
                {
                    cate[val]++;
                    tine[val][cate[val]] = (iul-1)*coloane + jul;
                }
            }
        }

        in++;
    }

    /*for(i=1; i <= sf; i++)
    {
        i_afis = coada[i]/coloane+1;
        j_afis = coada[i]%coloane;
        if(j_afis == 0)
        {
            i_afis--;
            j_afis = coloane;
        }
        fout << i_afis << ' ' << j_afis << '\n';
    }*/
    fout << sf;
}