Cod sursa(job #2579133)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 11 martie 2020 23:17:22
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
#define per pair <unsigned char, unsigned char>
#define xx first
#define yy second
#define UCH unsigned char
using namespace std;
ifstream in ("castel.in");
ofstream out("castel.out");
int dx[]={0, 1, 0, -1, 0};
int dy[]={0, 0, 1, 0, -1};
int n, m, k, rez=1;
bool accesabil[22510];
bitset <153> b[153];
vector <per> rem[22510];
short int neckey[153][153];
inline int tocode(int x, int y)
{
    return (x-1)*m+y;
}
inline per fromcode(int cod)
{
    int x=cod/m; x++;
    int y=cod%m;
    if(y==0) y=m, x--;
    return {(UCH) x, (UCH) y};
}
int main()
{
    in>>n>>m>>k;
    for(int i=0; i<=n+1; i++)
        b[i][0]=b[i][m+1]=1;
    for(int i=0; i<=m+1; i++)
        b[0][i]=b[n+1][i]=1;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            in>>neckey[i][j];
    queue <per> q;
    q.push(fromcode(k));
    per temp=fromcode(k);
    b[temp.xx][temp.yy]=1;
    accesabil[k]=true;
    while(!q.empty())
    {
        per elem=q.front(); q.pop();
        int codact=tocode(elem.xx, elem.yy);
        if(accesabil[codact]==false)
        {
            accesabil[codact]=true;
            while(!rem[codact].empty())
            {
                q.push({rem[codact].back().xx, rem[codact].back().yy}); rez++;
                rem[codact].pop_back();
            }
        }
        for(int i=1; i<=4; i++)
        {
            int xt=elem.xx+dx[i], yt=elem.yy+dy[i];

            if(b[xt][yt]==0)
            {
                b[xt][yt]=1;
                if(accesabil[neckey[xt][yt]]==true)
                    q.push( {(UCH)(xt), (UCH)(yt)} ), rez++;
                else
                    rem[neckey[xt][yt]].push_back({(UCH)(xt), (UCH)(yt)});
            }
        }
    }
    out<<rez;

    return 0;
}