Cod sursa(job #2661298)

Utilizator rARES_4Popa Rares rARES_4 Data 21 octombrie 2020 18:55:41
Problema Castel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream f ("castel.in");
ofstream g ("castel.out");
////////////////////////////////
struct punct
{
    int x,y;
} start;
struct camera
{
    int cheie;
    punct pct;
} camere[52600];
////////////////////////////////
queue<punct>q;
int n,m,k;
int matr[151][151];
bool chei[22600];
bool pasi[151][151];
int cnt = 1;
int dirx[] ={0,0,1,-1};
int diry[] = {1,-1,0,0};
////////////////////////////////
punct transformare_din_nr(int nr)
{
    int x,y;
    x = k/m + ((k%m) != 0);
    y = k%m;
    if(y == 0)
        y = m;
    return {x,y};
}
int transf_din_coordonate(int x,int y)
{
    return (x-1) * m + y;
}
punct poate_debloca_alta_usa(int cheie)
{
    for(int i = 1; i<=cnt; i++)
    {
        if(camere[i].cheie == cheie && !pasi[camere[i].pct.x][camere[i].pct.y])
        {
            camere[i].cheie = -1;
            return{camere[i].pct.x,camere[i].pct.y};
        }
    }
    return {-1,-1};
}
void lee()
{
    while(!q.empty())
    {
        int curentx = q.front().x;
        int curenty = q.front().y;
        q.pop();
        chei[transf_din_coordonate(curentx,curenty)] = 1;
        for(int i= 0; i<4; i++)
        {
            int newx = curentx+dirx[i];
            int newy = curenty+diry[i];
            if(!pasi[newx][newy])
            {
                if(chei[matr[newx][newy]])
                {
                    int cheie = transf_din_coordonate(newx,newy);
                    pasi[newx][newy] = 1;
                    q.push({newx,newy});
                    chei[cheie] = 1;
                    punct pct = poate_debloca_alta_usa(cheie);
                    while(pct.x!= -1 && pct.y!=-1)
                    {
                        if(!pasi[pct.x][pct.y])
                        {
                            q.push(pct);
                            pasi[pct.x][pct.y] = 1;
                        }
                       pct = poate_debloca_alta_usa(cheie);
                    }
                }
                else
                {
                    camere[cnt].cheie = matr[newx][newy];
                    camere[cnt++].pct = {newx,newy};
                }
            }
        }
    }
}
void bordare()
{
    for(int i = 0;i<=n+1;i++)
        pasi[i][0] = pasi[i][m+1] = 1;
    for(int i = 0;i<=m+1;i++)
        pasi[0][i] = pasi[n+1][i] = 1;
}
int main()
{
    f >> n >> m >> k;
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=m;j++)
            f >> matr[i][j];
    }
    chei[k] = 1;
    start = transformare_din_nr(k);
    bordare();
    q.push(start);
    pasi[start.x][start.y] = 1;
    lee();
    int poate_intra = 0;
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=m;j++)
            poate_intra+=(pasi[i][j]);
    }
    g << poate_intra;

}