Cod sursa(job #682025)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 18 februarie 2012 14:40:56
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.37 kb
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

#define MAX 155

using namespace std;

int n, m, start, total;
int matrice[MAX][MAX];
bool parcurs[MAX][MAX];
bool chei[MAX * MAX];
int depl_x[] = {-1, 0, 1, 0};
int depl_y[] = {0, 1, 0, -1};

struct coada
{
    int x, y, cod;
};

vector<coada> visit;
map<int, vector<coada> > unopened;
vector<coada> adauga;

void citire()
{
    freopen("castel.in", "r", stdin);
    scanf("%d %d %d", &n, &m, &start);
    int i, j;
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m; j++)
        {
            scanf("%d", &matrice[i][j]);
        }
    }
    total = 1;
    fclose(stdin);
}

void deschide(int cheie)
{
    unsigned int i;
    if(unopened.count(cheie))
    {
        for(i = 0; i < unopened[cheie].size(); i++)
        {
            visit.push_back(unopened[cheie][i]);
            chei[unopened[cheie][i].cod] = true;
            parcurs[unopened[cheie][i].x][unopened[cheie][i].y] = true;
            deschide(unopened[cheie][i].cod);
        }
    }
    unopened.erase(cheie);
}

void solve()
{
    chei[start] = true;
    coada adaugare;
    adaugare.x = start / m + 1;
    adaugare.y = start % m;
    if(!adaugare.y)
    {
        adaugare.x--;
        adaugare.y = m;
    }
    adaugare.cod = start;
    parcurs[adaugare.x][adaugare.y] = true;
    visit.push_back(adaugare);
    unsigned int a = 0;
    int i;
    while(a < visit.size())
    {
        for(i = 0; i != 4; i++)
        {
            if(visit[a].x + depl_x[i] > 0 && visit[a].x + depl_x[i] <= n &&
                    visit[a].y + depl_y[i] > 0 && visit[a].y + depl_y[i] <= m &&
                    !parcurs[visit[a].x + depl_x[i]][visit[a].y + depl_y[i]])
            {
                if(chei[matrice[visit[a].x + depl_x[i]][visit[a].y + depl_y[i]]])
                {
                    adaugare.x = visit[a].x + depl_x[i];
                    adaugare.y = visit[a].y + depl_y[i];
                    adaugare.cod = m * (adaugare.x - 1) + adaugare.y;
                    parcurs[visit[a].x + depl_x[i]][visit[a].y + depl_y[i]] = true;
                    chei[adaugare.cod] = true;
                    visit.push_back(adaugare);
                    deschide(adaugare.cod);
                }
                else
                {
                    adaugare.x = visit[a].x + depl_x[i];
                    adaugare.y = visit[a].y + depl_y[i];
                    adaugare.cod = m * (adaugare.x - 1) + adaugare.y;
                    parcurs[adaugare.x][adaugare.y] = true;
                    if(unopened.count(matrice[visit[a].x + depl_x[i]][visit[a].y + depl_y[i]]))
                    {
                        unopened[matrice[visit[a].x + depl_x[i]][visit[a].y + depl_y[i]]].push_back(adaugare);
                    }
                    else
                    {
                        adauga.push_back(adaugare);
                        unopened.insert(pair<int, vector<coada> >(matrice[visit[a].x + depl_x[i]][visit[a].y + depl_y[i]], adauga));
                        adauga.clear();
                    }
                }
            }
        }
        a++;
    }
}

void afisare()
{
    freopen("castel.out", "w", stdout);
    printf("%d", visit.size());
    fclose(stdout);
}

int main()
{
    citire();
    solve();
    afisare();
    return 0;
}