Cod sursa(job #2700794)

Utilizator eugen5092eugen barbulescu eugen5092 Data 28 ianuarie 2021 20:14:42
Problema Castel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <bits/stdc++.h>
using namespace std;

ifstream ci("castel.in");
ofstream cou("castel.out");

struct coord{
    int x,y;
};

int n,m,k;
int v[200][200];
int trecut[200][200];
int codate[40000];

short coordx[]={-1,0,1,0};
short coordy[]={0,1,0,-1};

queue<coord>q;

void citire(){
    ci>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ci>>v[i][j];
        }
    }
}

coord transfm(int p){
    coord w;
    w.x=p/n+1;
    if(p%n==0){
        w.y=n;
        w.x--;
    }else{
        w.y=p%n;

    }
    return w;
}
//iau ce e in aia
//pn inapoi alea de nu am cheie pt ele
//marchez cu 1

//iau vecini nemarcati
//pun iar

bool verif(int x,int y){
    return x>=1&&y>=1&&x<=n&&y<=m;
}

void iavec(coord a){
    int x,y;
    int x1,y1;
    x=a.x;
    y=a.y;
    coord sl;

    for(int i=0;i<=3;i++){

        x1=x+coordx[i];
        y1=y+coordy[i];
        //cout<<x<<" "<<y<<" "<<x1<<" "<<y1<<" \n";
        if(verif(x1,y1)){
            if(trecut[x1][y1]==0){
                sl.x=x1;
                sl.y=y1;
                q.push(sl);
                //cout<<"pus \n";
            }
        }
    }



}

int rezcoada(){
    //cout<<" \n p \n";
    coord a[40005];
    int t=0;
    int faiar=0;
    while(!q.empty()){
        if(!(a[t].x==q.front().x&&a[t].y==q.front().y)){
            a[++t]=q.front();
        }
        q.pop();
    }
    int cod;
    for(int i=1;i<=t;i++){
        //cout<<a[i].x<<" "<<a[i].y<<" ";
        cod=v[a[i].x][a[i].y];
        //cout<<cod<<" "<<codate[cod]<<"\n";
        if(codate[cod]==0){
            q.push(a[i]);
        }else{
            faiar=1;
            trecut[a[i].x][a[i].y]=1;
        }
    }
    //cout<<"\n";
    for(int i=1;i<=t;i++){
        cod=v[a[i].x][a[i].y];
        if(codate[cod]==1){
            iavec(a[i]);
            int t=(a[i].x-1)*m+a[i].y;
            //cout<<t<<"\n";
            codate[t]=1;
        }
    }
    //cout<<"\n\n";
    return faiar;

}

void rez(){
    int x,y;
    coord w;
    w=transfm(k);
    x=w.x;
    y=w.y;
    codate[(x-1)*m+y]=1;
    trecut[x][y]=1;

    int x1,y1;
    coord sl;
    for(int i=0;i<=3;i++){
        x1=x+coordx[i];
        y1=y+coordy[i];
        if(verif(x1,y1)){
            if(trecut[x1][y1]==0){
                sl.x=x1;
                sl.y=y1;
                q.push(sl);
            }
        }
    }

    while(rezcoada()){
        //nimic
    }
    int cn=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(trecut[i][j]==1 ){
                cn++;
            }
        }
    }
    cou<<cn;
}

int main()
{
    citire();
    rez();

    return 0;
}