Cod sursa(job #682001)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 18 februarie 2012 13:48:08
Problema Castel Scor 90
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;
    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;
}