Cod sursa(job #1895376)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 27 februarie 2017 22:10:13
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream f ("castel.in");
ofstream g ("castel.out");
int n,m,xp,yp,cam,i,j,v[153][153],can[150*150+1],raspuns,xx,yy,cx,cy,dx[]={-1,0,1,0},dy[]={0,1,0,-1};
bool viz[153][153];
queue <int> qx;
queue <int> qy;
vector <int> key;
vector <int> vx;
vector <int> vy;
bool apartine(int x,int y)
{
    return x>=1&&x<=n&&y>=1&&y<=m;
}
void read()
{
    f>>n>>m>>xp;
    yp=xp%m;
    cam=xp;
    if(!yp) {yp=m;--xp;}
    xp=xp/n+1;
    viz[xp][yp]=1;
    qx.push(xp);
    qy.push(yp);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j) f>>v[i][j];
    }
    can[cam]=v[xp][yp];
    raspuns=1;
}
int codific(int x,int y)
{
    return (x-1)*m+y;
}
void lee()
{
    while(!qx.empty())
    {
        xx=qx.front();
        yy=qy.front();
        qx.pop();
        qy.pop();
        for(int i=0;i<4;++i)
        {
            cx=xx+dx[i];
            cy=yy+dy[i];
            if(apartine(cx,cy)&&!viz[cx][cy])
            {
                if(can[v[cx][cy]])
                {
                    viz[cx][cy]=1;
                    ++raspuns;
                    qx.push(cx);
                    qy.push(cy);
                    can[codific(cx,cy)]=1;
                    for(int j=0;j<key.size();++j)
                    {
                        if(key[j]==codific(cx,cy))
                        {
                            viz[vx[j]][vy[j]]=1;
                            qx.push(vx[j]);
                            qy.push(vy[j]);
                            key.erase(key.begin()+j);
                            vx.erase(vx.begin()+j);
                            vy.erase(vy.begin()+j);
                            --j;
                            ++raspuns;
                        }
                    }
                }
            }
            else
            {
                key.push_back(v[cx][cy]);
                vx.push_back(cx);
                vy.push_back(cy);
            }
        }
    }
}
int main()
{
    read();
    lee();
    g<<raspuns+1;
    return 0;
}