Cod sursa(job #1793200)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 30 octombrie 2016 20:18:48
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <stdio.h>
#define FOR(i, a, b) for (i = (a); i <= (b); i++)
#define FORD(i, a, b) for (i = (a); i >= (b); i--)
#define MaxN 151
#define MaxK 130001

typedef struct NOD {
    int x, y;
    NOD* next;
} *PNOD;

PNOD L[MaxK];

const int di[] = {-1, 0, 1, 0}, dj[] = {0, 1, 0, -1};

int N, M, K;
int a[MaxN][MaxN], ch[MaxN][MaxN], open[MaxN][MaxN], sel[MaxK];
int is, js;
int chei[MaxK], kchei, st, dr;
int nrd;

FILE *fout = fopen("castel.out", "wt");

void Add(int i, int ii, int jj)
{
    PNOD p = new NOD;
    p->x = ii, p->y = jj;
    p->next = L[i];
    L[i] = p;
}

void fill(int i, int j)
{
    if (i < 1 || j < 1 || i > M || j > N) return;
    if (open[i][j]) return;
    if (sel[a[i][j]] || (i == is && j == js))
    {
        ++nrd;
        chei[++dr] = ch[i][j];
        open[i][j] = 1;
        int d;
        FOR (d, 0, 3)
            fill(i + di[d], j + dj[d]);
    }
    else
    {
        //fprintf(fout, "%d %d %d\n", i, j, a[i][j]);
        Add(a[i][j], i, j);
    }
}

int main()
{
    int i, j, k, iv, jv, d;

    FILE *fin = fopen("castel.in", "rt");

    fscanf(fin, "%d %d %d", &M, &N, &K);
    FOR (i, 1, M)
        FOR (j, 1, N)
            fscanf(fin, "%d", &a[i][j]);

    /*FOR (i, 1, M)
    {
        FOR (j, 1, N)
            fprintf(fout, "%d ", ch[i][j]);
        fprintf(fout, "\n");
    }*/

    k = 0;
    FOR (i, 1, M)
        FOR (j, 1, N)
        {
            ch[i][j] = ++k;
            if (k == K) is = i, js = j;
        }

    //chei[++kchei] = K;
    //fprintf(fout, "%d %d", is, js);
    sel[K] = 1;
    st = 1, dr = 0;
    //++nrd;

    fill(is, js);

    /*FOR (d, 0, 3)
    {
        iv = is + di[d], jv = js + dj[d];
        if (iv >= 1 && jv >= 1 && iv <= M && jv <= N)
        {
            if (sel[a[iv][jv]])
            {
                Add(a[iv][jv], iv, jv);
                chei[++dr] = ch[iv][jv];
            }
        }
    }*/

    //fprintf(fout, "%d %d\n", st, dr);
    //for (i = 1; i <= dr; i++)
    //    fprintf(fout, "%d\n", chei[i]);

    while (st <= dr)
    {
        //fprintf(fout, "%d\n", chei[st]);
        sel[chei[st]] = 1;
        for (PNOD p = L[chei[st]]; p; p=p->next)
        {
            //if (open[p->x][p->y]) continue;
            fill(p->x, p->y);
        }
        ++st;
    }

    fprintf(fout, "%d\n", nrd);
    fclose(fin);
    fclose(fout);

    return 0;
}