Pagini recente » Cod sursa (job #406571) | Cod sursa (job #235029) | Cod sursa (job #3264420) | Cod sursa (job #226484) | Cod sursa (job #3281894)
#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;
}