Cod sursa(job #2231958)

Utilizator georgitTreista Georgiana georgit Data 16 august 2018 19:02:19
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <vector>
#include <queue>
#define N 155

using namespace std;

int a[N][N],n,m;
bool viz[N][N],iskey[N*N];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
queue <int> Q;
vector <int> cameredeschise[N*N];
int linie(int k)
{
    return k/m+(k%m!=0);
}
int coloana(int k)
{
    int c=k%m;
    if(c==0)
        return m;
    return c;
}
bool isinside(int x,int y)
{
    return (x>=1 and x<=n and y>=1 and y<=m);
}
int room(int x,int y)
{
    if(y==m)
        return x*m;
    return (x-1)*m+y;
}
int main()
{
    ifstream f("castel.in");
    ofstream g("castel.out");
    int k;
    f>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f>>a[i][j];
    Q.push(k);
    int l=linie(k);
    int c=coloana(k);
    viz[l][c]=1;
    int nrcamere=0;
    while(!Q.empty())
    {
        nrcamere++;
        int key=Q.front();
        iskey[key]=1;
        Q.pop();
        for(int i=0;i<cameredeschise[key].size();i++)
        {
            int camera=cameredeschise[key][i];
            int l=linie(camera);
            int c=coloana(camera);
            if(viz[l][c]==0)
            {
               viz[l][c]=1;
               Q.push(camera);
            }
        }
        int l=linie(key);
        int c=coloana(key);
        for(int d=0;d<4;d++)
        {
            int x=l+dx[d];
            int y=c+dy[d];
            if(isinside(x,y) and viz[x][y]==0)
            {
                if(iskey[a[x][y]])
                {
                    viz[x][y]=1;
                    Q.push(room(x,y));
                }
                else
                    cameredeschise[a[x][y]].push_back(room(x,y));
            }
        }
    }
    g<<nrcamere<<" ";
    return 0;
}