Cod sursa(job #1666913)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 28 martie 2016 14:53:26
Problema Castel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <fstream>
#define mod 20000

using namespace std;

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

int n, m, k, i, j, xi, yi;
int a[155][155];
struct {int x,y;} neviz[22555][1000];
int nv[22555];
bool cheie[22555], b[155][155];
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 calcul()
{
    int coada[2][mod];
    int x, y, xx, yy;
    int st = 0, dr = 0;
    coada[0][st] = xi, coada[1][st] = yi;
    cheie[(xi-1)*m+yi] = 1;
    while (st <= dr)
    {
        x = coada[0][st], y = coada[1][st];
        for (i = 1; i <= nv[a[x][y]]; i++)
        {
            cheie[(neviz[a[x][y]][i].x-1)*m+neviz[a[x][y]][i].y] = 1;
            dr++;
            coada[0][dr] = neviz[a[x][y]][i].x;
            coada[1][dr] = neviz[a[x][y]][i].y;
        }
        for (i = 0; i < 4; i++)
        {
            xx = x+dx[i], yy = y+dy[i];
            //g << xx << " "<< yy << '\n';
            if (inauntru(xx, yy) && cheie[(xx-1)*m+yy] == 0)
            {
                if (cheie[a[xx][yy]] == 1)
                {
                    cheie[(xx-1)*m+yy] = 1;
                    dr++;
                    coada[0][dr] = xx, coada[1][dr] = yy;
                }
                else
                {
                    nv[a[xx][yy]]++;
                    neviz[a[xx][yy]][nv[a[xx][yy]]].x = xx;
                    neviz[a[xx][yy]][nv[a[xx][yy]]].y = yy;
                }
            }
        }
        st++;
    }
}

int main()
{
    f >> n >> m >> k;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            f >> a[i][j];

    if (k%m == 0)
        yi = m;
    else
        yi = k%m;

    xi = k/m+(k%m > 0);
    calcul();
    int nr = 0;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (cheie[(i-1)*m+j] == 1)
                nr++;
    g << nr;
    return 0;
}