Cod sursa(job #574620)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 7 aprilie 2011 12:53:02
Problema Lapte Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#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;}