Pagini recente » Cod sursa (job #1744286) | Cod sursa (job #1164272) | Cod sursa (job #681031) | Cod sursa (job #1718313) | Cod sursa (job #574620)
Cod sursa(job #574620)
#include <cstdio>
#include <fstream>
#include <queue>
using namespace std;
#define N 128
#define mp make_pair
#define f first
#define s second
const int di[]={1,-1,0,0},
dj[]={0,0,1,-1};
int a[N][N];
int n;
int vrf (int i,int j){
int k=0;
for(;i+k<=n&&j+k<=n&&a[i][j+k]==1&&a[i+k][j]==1&&a[i+k][j+k]==1;++k);
--k;
return k;}
void fill (int ii,int jj ,int k ){
for(int i=ii;i<=ii+k;++i)
for(int j=jj;j<=jj+k;++j)
a[i][j]=-1;
}
void lee (){
queue<pair<int,int> > q;
a[1][1]=1;
for(q.push(mp(1,1));!q.empty();q.pop()){
pair<int ,int > x=q.front();
for(int k=0;k<4;++k){
int i=x.f+di[k],j=x.s+dj[k];
if(i<=n&&j<=n&&i>=1&&j>=1&&a[i][j]==0){
a[i][j]=a[x.f][x.s]+1;
q.push(mp(i,j));
}
}
}
}
void drum (int i,int j){
if(a[i][j]==1){
printf("%d %d\n",i,j);
return ;
}
else
for(int k=0;k<4;++k)
if(a[i][j]==a[i+di[k]][j+dj[k]]+1){
drum(i+di[k],j+dj[k]);
printf("%d %d\n",i,j);
return ;
}
}
int main ()
{
int c=0;
ifstream in ("lacuri.in");
freopen ("lacuri.out","w",stdout);
in>>n;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
in>>a[i][j];
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(a[i][j]==1){
++c;
fill(i,j,vrf(i,j));
}
printf("%d\n",c);
lee ();
drum (n,n);
return 0;}