Cod sursa(job #1666532)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 28 martie 2016 08:30:34
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <fstream>
#define mod 20000
#define Mod 100
#define cod(x,y) (x-1)*m+y

using namespace std;

ifstream f("castel.in");
ofstream g("castel.out");

int n, m, i, j, k, a[151][151], xi, yi;
int trb[151][151];
int coada[2][mod], st = 0, dr = 0;
bool fol[151][151];
bool cheie[22555];
struct
{
    int x, y;
}ramas[22255][Mod];
int S[22555], D[22555];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

bool inauntru(int x, int y)
{
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}

void pune_in_coada(int xx, int yy)
{
    dr++;
    coada[0][dr%mod] = xx;
    coada[1][dr%mod] = yy;
}

void pune_in_alta_coada(int cheie, int xx, int yy)
{
    D[cheie]++;
    ramas[cheie][D[cheie]%Mod].x = xx;
    ramas[cheie][D[cheie]%Mod].y = yy;
}

void pune_dintr_o_coada_in_alta(int cheie)
{
    dr++;
    coada[0][dr%mod] = ramas[cheie][S[cheie]%Mod].x;
    coada[1][dr%mod] = ramas[cheie][S[cheie]%Mod].y;
    S[cheie]++;
}

void cauta()
{
    int x, y, xx, yy;
    int i;
    coada[0][st] = xi, coada[1][st] = yi;
    fol[xi][yi] = 1;
    cheie[(xi-1)*m+yi] = 1;
    int val1;
    while (st <= dr)
    {
        x = coada[0][st%mod], y = coada[1][st%mod];
        val1 = cod(x,y);
        //g << val1 << " ";
        for (i = 1; i <= D[val1]; i++)
        {
            int X = ramas[val1][i%Mod].x;
            int Y = ramas[val1][i%Mod].y;
            fol[X][Y] = 1;
            //g << cod(X,Y) << " ";
            pune_in_coada(X, Y);
        }
        for (i = 0; i < 4; i++)
        {
            xx = x+dx[i], yy = y+dy[i];
            if (inauntru(xx, yy) && cheie[cod(xx,yy)] == 0)
            {
                if (cheie[a[xx][yy]] == 1)
                {
                    pune_in_coada(xx,yy);
                    fol[xx][yy] = 1;
                    cheie[cod(xx,yy)] = 1;
                }
                else
                    pune_in_alta_coada(a[xx][yy], xx, yy);
            }
        }
        st++;
    }
}

int main()
{
    f >> n >> m >> k;
    xi = k/m+(k%m>0), yi = k%m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            f >> a[i][j], trb[i][j] = cod(i,j);
    cauta();
    int cnt = 0;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        //{
            if (fol[i][j] == 1)
                cnt++;
    }
    g << cnt;
    return 0;
}