Cod sursa(job #2309158)

Utilizator 0738076326Simon Wil 0738076326 Data 28 decembrie 2018 15:27:41
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.9 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream f("rover.in");
ofstream g("rover.out");

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

int n,c,mat[501][501],nr;
int a[501][501];

void afisarea(){
    int i,j;
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++)
            g<<a[i][j]<<" ";
        g<<"\n";
    }
}

void afisaremat(){
    int i,j;
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++)
            g<<mat[i][j]<<" ";
        g<<"\n";
    }
}

void fills(int x, int y){
    mat[x][y]=-1;

    int i;
    for(i=0; i<4; i++){
        int nx=x+dx[i];
        int ny=y+dy[i];

        if(!mat[nx][ny])
            fills(nx, ny);
    }

}

void Lee(){
    int nx,ny,i,x,y;
    deque<int> qx, qy, qqx, qqy;

    if(a[1][1]==1){
        qqx.push_back(1);
        qqy.push_back(1);
    }
    else{
    qx.push_back(1);
    qy.push_back(1);}
    mat[1][1]=1;
    qqx.push_back(-1);
    while(!qqx.empty()){
            if(qqx.back()==-1)
                qqx.pop_back();

    while(!qqx.empty()){
        qx.push_back(qqx.front());
        qy.push_back(qqy.front());
        qqx.pop_front();
        qqy.pop_front();
    }

    while(!qx.empty()){
        x=qx.front();
        y=qy.front();
        qx.pop_front();
        qy.pop_front();

        for(i=0; i<4; i++){
            nx=x+dx[i];
            ny=y+dy[i];
            if(!mat[nx][ny] && !a[nx][ny]){
                qx.push_back(nx);
                qy.push_back(ny);
                mat[nx][ny]=mat[x][y]+1;

            }
            else
            if(!mat[nx][ny]){
                qqx.push_back(nx);
                qqy.push_back(ny);
                mat[nx][ny]=mat[x][y]+2;
            }
        }
    }
    }
}

void rezolvare1(){
    int i,j,x;
    f>>n>>c;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++){
        f>>x;
        if(x<c)
            a[i][j]=0;
        else
            a[i][j]=1;

        mat[i][j]=a[i][j];
        }

    for(i=0; i<=n+1; i++)
        a[i][0]=a[0][i]=a[i][n+1]=a[n+1][i]= mat[i][0]=mat[0][i]=mat[i][n+1]=mat[n+1][i]=-1;

   if(!a[1][1] && !a[n][n]){
        fills(1,1);
        if(mat[n][n]==-1)
                g<<0;
        else{
            for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
            mat[i][j]=0;

           Lee();
         // afisaremat();



           i=j=n;

            while(i!=1 || j!=1){
                bool ok=0;
                int nx,ny;

                for(int o=0; o<4 && !ok; o++){
                    nx=i+dx[o];
                    ny=j+dy[o];
                  if(mat[nx][ny]==mat[i][j]-1)
                    {
                       // g<<i<<" "<<j<<" "<<nx<<" "<<ny<<"\n";
                       // g<<mat[i][j]<<" "<<mat[nx][ny]<<"\n";
                        i=nx;
                        j=ny;
                        ok=1;
                    }
                }

            if(!ok){
                    ok=0;
             for(int o=0; o<4 && !ok; o++){
                    nx=i+dx[o];
                    ny=j+dy[o];
                    if(mat[nx][ny]==mat[i][j]-2)
                    {

                        nr++;
                        i=nx;
                        j=ny;
                        ok=1;
                    }
                }
            }

            if(!ok)
                i=j=n;

            }
            g<<nr;

           // g<<"\n"<<mat[4][2]<<" "<<mat[4][1];

        }
    }
    else{
         for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
            mat[i][j]=0;

           Lee();
         // afisarea();
         // afisaremat();



           i=j=n;

            while(i!=1 || j!=1){
                bool ok=0;
                int nx,ny;

                for(int o=0; o<4 && !ok; o++){
                    nx=i+dx[o];
                    ny=j+dy[o];
                  if(mat[nx][ny]==mat[i][j]-1)
                    {
                      //  g<<i<<" "<<j<<" "<<nx<<" "<<ny<<"\n";
                     //   g<<mat[i][j]<<" "<<mat[nx][ny]<<"\n";
                        i=nx;
                        j=ny;
                        ok=1;
                    }
                }

            if(!ok){
                    ok=0;
             for(int o=0; o<4 && !ok; o++){
                    nx=i+dx[o];
                    ny=j+dy[o];
                    if(mat[nx][ny]==mat[i][j]-2)
                    {

                        nr++;
                        i=nx;
                        j=ny;
                        ok=1;
                    }
                }
            }

            if(!ok)
                i=j=n;

            }
            if(a[n][n])
                nr++;
            g<<nr;
    }
   //afisaremat();
}

int main(){
    int p;
    f>>p;
    if(p==1)
        rezolvare1();
    else
        g<<2;


    return 0;
}