Cod sursa(job #3281894)

Utilizator Martin_BohonyiMartin Bohonyi Martin_Bohonyi Data 3 martie 2025 21:49:43
Problema Barbar Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.79 kb
#include<fstream>
#include<cmath>
#include<queue>

using namespace std;

ifstream fin("lacuri.in");
ofstream fout("lacuri.out");

bool Ok=true;
int N , F[101][101] , CntPatrate , A , L[101][101];
int LinMinn , LinMaxx , ColMaxx , ColMinn;

queue<pair<int,int>>Q;

bool inmat(int i , int j){
     return i>=1 && i<=N && j>=1 && j<=N;
 }

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

void Fill(int LinS , int ColS){
     F[LinS][ColS]=0;
     Q.push(make_pair(LinS,ColS));
     while(!Q.empty()){
        int Lin1=Q.front().first , Col1=Q.front().second;
        LinMinn=min(LinMinn,Lin1);
        ColMinn=min(ColMinn,Col1);
        LinMaxx=max(LinMaxx,Lin1);
        ColMaxx=max(ColMaxx,Col1);
        A++;
        Q.pop();
        for(int k=0 ; k<4 ; k++){
            int Lin2=Lin1+dx[k] , Col2=Col1+dy[k];
            if(inmat(Lin2,Col2)){
                 if(F[Lin2][Col2] == 1){
                    F[Lin2][Col2]=0;
                    Q.push(make_pair(Lin2,Col2));
                 }
            }
        }
     }
 }

void Lee(){
     Q.push(make_pair(1,1));
     L[1][1]=1;
     while(!Q.empty()){
        int Lin1=Q.front().first , Col1=Q.front().second;
        Q.pop();
        for(int k=0 ; k<4 ; k++){
            int Lin2=Lin1+dx[k] , Col2=Col1+dy[k];
            if(inmat(Lin2,Col2)){
                if(L[Lin2][Col2] == 0){
                    L[Lin2][Col2]=L[Lin1][Col1]+1;
                    Q.push(make_pair(Lin2,Col2));
                }
            }
        }
     }
 }

void Traseu(int Lin , int Col){
    if(Lin==1 && Col==1){
        fout<<Lin<<' '<<Col<<'\n';
        return;
    }
    for(int k=0 ; k<4 ; k++){
         int Lin2=Lin-dx[k] , Col2=Col-dy[k];
         if(inmat(Lin2,Col2)){
             if(L[Lin][Col] == L[Lin2][Col2] + 1){
                   Traseu(Lin2,Col2);
                   fout<<Lin<<' '<<Col<<'\n';
                   break;
             }
         }

    }
 }

void Rezolvare_Cerinta2(){
    Lee();
    Traseu(N,N);
  }

int main()
{
fin>>N;
for(int i=1 ; i<=N ; i++)
    for(int j=1 ; j<=N ; j++){
        fin>>F[i][j];
        if(F[i][j] == 1)
              L[i][j]=-1;
    }

for(int i=1 ; i<=N ; i++)
    for(int j=1 ; j<=N ; j++)
        if(F[i][j] == 1){
            LinMinn=N+1 , LinMaxx=0 , ColMinn=N+1 , ColMaxx=0;
            A=0;
            Fill(i,j);
            if(sqrt(A) == (int)sqrt(A)){
                if((LinMaxx-LinMinn+1)*(ColMaxx-ColMinn+1) == A){
                    CntPatrate++;
                }
                else{
                    Ok=false;
                    break;
                }
            }
            else{
                Ok=false;
            }
        }

fout<<CntPatrate<<'\n';
if(Ok){
    Rezolvare_Cerinta2();
 }


return 0;
}