Cod sursa(job #2347073)

Utilizator mihaimodiMihai Modi mihaimodi Data 18 februarie 2019 13:12:16
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <fstream>
#include <queue>
using namespace std;
int a[151][151],b[151][151];
bool chei[22501];
int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};
int n,m,x,lin,col,sol,st=1,dr=1;
ifstream fin("castel.in");
ofstream fout("castel.out");
vector <int> key[22501];
struct coada
{
    int l,c;
}q[22501];
int camera(int l,int c)
{
    return m*(l-1)+c;
}
void coord(int v, int&l,int &c)
{
    int r=v%m;
    l=v/m;c=r;
    if(r==0)
        c=m;
   else
     l++;
}
int inrange(int x, int y)
{
    return x>0&&y>0&&x<=n&&y<=m;
}
int main()
{
    fin>>n>>m>>x;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            fin>>a[i][j];
    coord(x,lin,col);
    chei[x]=1;
    q[st].l=lin;
    q[st].c=col;
    b[lin][col]=2;
    while(st<=dr)
    {
        int l=q[st].l;
        int c=q[st].c;
        int cameraC=camera(l,c);
        for(int j=0;j<key[cameraC].size();j++)
        {
            int ln,cn;
            coord(key[cameraC][j],ln,cn);
            if(b[ln][cn]!=2){
                dr++;
                q[dr].l=ln;
                q[dr].c=cn;
                b[ln][cn]=2;
                chei[camera(ln,cn)]=1;
            }
        }

        for(int i=1;i<=4;i++)
        {
            int ln=l+dx[i];
            int cn=c+dy[i];
            if(inrange(ln,cn))
            {
                if(chei[a[ln][cn]]==1&&b[ln][cn]!=2)
                {
                    dr++;
                    q[dr].l=ln;
                    q[dr].c=cn;
                    int cameraC=camera(ln,cn);
                    chei[cameraC]=1;
                    b[ln][cn]=2;
                }
                else if(b[ln][cn]==0&&chei[a[ln][cn]]==0)
                {
                    key[a[ln][cn]].push_back(camera(ln,cn));
                    b[ln][cn]=1;
                }
            }
        }
        st++;
    }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(b[i][j]==2)
                sol++;
    fout<<sol;
    return 0;
}