Cod sursa(job #2269277)

Utilizator AndoneAlexandruAndone Alexandru AndoneAlexandru Data 25 octombrie 2018 20:31:00
Problema Castel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <fstream>
#include <queue>
using namespace std;

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

queue<pair<int, int> >q;
int di[] = {1, 0, -1, 0};
int dj[] = {0, 1, 0, -1};

int room[160][160];
int key[160][160];
int keys[22500];
int n, m, k;
int liPr, coPr, nrKeys;

void citire();
void lee(int);
bool ifkey(int, int);

void afisare_matrice();

int main()
{
    citire();

    keys[nrKeys] = room[liPr][coPr];
    nrKeys++;
    bool ok = true;
    int visit = -1;
    while (ok == true)
    {
        int aux = nrKeys;
        lee(visit);
        visit--;
        if (nrKeys == aux) ok = false;
    }
    g << nrKeys;
    return 0;
}

void citire()
{
    f >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            f >> key[i][j];
            room[i][j] = (i-1)*(n-1) + j;
            if (room[i][j] == k)
            {
                liPr = i;
                coPr = j;
            }
        }
    }
}

void bordare()
{
    for (int i = 0; i <= n+1; i++)
    {
        room[i][0] = 0;
        room[i][m+1] = 0;
    }
    for (int j = 0; j <= m+1; j++)
    {
        room[0][j] = 0;
        room[n+1][j] = 0;
    }
}

bool ifkey(int x, int y)
{
    for (int i = 0; i < nrKeys; i++)
        if (key[x][y] == keys[i])
            return true;
    return false;
}

void lee(int visit)
{
    room[liPr][coPr] = visit;
    q.push(make_pair(liPr, coPr));
    while(!q.empty())
    {
        pair<int, int>p = q.front();
        q.pop();
        for (int k = 0; k < 4; k++)
        {
            if (room[p.first+di[k]][p.second+dj[k]] > 0 && ifkey(p.first+di[k], p.second+dj[k]) == true)
            {
                keys[nrKeys] = room[p.first+di[k]][p.second+dj[k]];
                nrKeys++;
                room[p.first+di[k]][p.second+dj[k]] = visit;
                q.push(make_pair(p.first+di[k], p.second+dj[k]));
            }
            else if (room[p.first+di[k]][p.second+dj[k]] == visit)
            {
                room[p.first+di[k]][p.second+dj[k]] = visit-1;
                q.push(make_pair(p.first+di[k], p.second+dj[k]));
            }
        }
    }
}

void afisare_matrice()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            g << room[i][j] << " ";
        g << "\n";
    }
    g << "\n\n" << nrKeys;
}