Cod sursa(job #1666099)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 27 martie 2016 17:47:51
Problema Castel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>
#define mod 20000
#define mod2 mod/20
#define KEY(x,y) a[x][y]
#define pune_in_coada(xx, yy) dr++, coada[0][dr%mod] = xx, coada[1][dr%mod] = yy;

using namespace std;

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

short xi, yi, n, m, k, i, j, nr, a[152][152];
bool b[152][152], cheie[22555];
short incerc[152][152];
short 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 cauta()
{
    int i, x, y, xx, yy;
    int coada[2][mod], st = 0, dr = 0;
    struct
    {
        int x, y;
    }neviz[151][mod2];
    int st2[151] = {0}, dr2[151] = {0};

    coada[0][st] = xi, coada[1][st] = yi;
    cheie[(xi-1)*m+yi] = 1;
    while (st <= dr)
    {
        x = coada[0][st%mod], y = coada[1][st%mod];
        b[x][y] = 1;
        for (i = 0; i < 4; i++)
        {
            xx = x+dx[i], yy = y+dy[i];
            if (inauntru(xx, yy) && b[xx][yy] == 0)
            {
                int val1 = a[xx][yy];
                if (cheie[val1] == 1)
                {
                    pune_in_coada(xx, yy);
                    b[xx][yy] = 1;
                    cheie[(xx-1)*m+yy] = 1;
                    pune_in_coada(neviz[val1][dr2[val1]].x, neviz[val1][dr2[val1]].y);
                    st2[val1]++;
                }
                else
                {
                    dr2[val1]++;
                    neviz[val1][dr2[val1]].x = xx;
                    neviz[val1][dr2[val1]].y = xx;
                }
            }
        }
        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];
    cauta();
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (b[i][j] == 1)
                nr++;
    g << nr;
    return 0;
}