Cod sursa(job #1003281)

Utilizator cristigrigoreGrigore Cristan Andrei cristigrigore Data 30 septembrie 2013 10:58:40
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <fstream>
#include <cstring>
#define inf 10000
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
const int dx[]={-1,-1,0,1,1,1,0,-1};
const int dy[]={0,1,1,1,0,-1,-1,-1};
int k,N,M,i,j,xr,yr,xj,yj,px,py,Min,a[200][200],z1,z2,b[200][200];
char c[1001];
bool verif(int x,int y)
{
    if(x>N || y>M || x<0 || y<0 || a[x][y]==-1) return true;
    return false;
}
bool verif1(int x,int y)
{
    if(x>N || y>M || x<0 || y<0 || b[x][y]==-1) return true;
    return false;
}

void lee()
{
    int i,xx,yy,x,y;
    bool ok;
    ok=true;
    while(ok)
    {
        ok=false;
        for(x=1; x<=N; x++)
        for(y=1; y<=M; y++)
        {
            if(verif(x,y)==true || a[x][y]==inf) continue;
            for(i=0; i<=7; i++)
            {
                xx=x+dx[i];
                yy=y+dy[i];
                if(verif(xx,yy)==true) continue;
                if(a[xx][yy]>a[x][y]+1) {a[xx][yy]=a[x][y]+1;ok=true;}
            }
        }
    }
}
void lee1()
{
    int i,xx,yy,x,y;
    bool ok;
    ok=true;
    while(ok)
    {
        ok=false;
        for(x=1; x<=N; x++)
        for(y=1; y<=M; y++)
        {
            if(verif1(x,y)==true || b[x][y]==inf) continue;
            for(i=0; i<=7; i++)
            {
                xx=x+dx[i];
                yy=y+dy[i];
                if(verif1(xx,yy)==true) continue;
                if(b[xx][yy]>b[x][y]+1) {b[xx][yy]=b[x][y]+1;ok=true;}
            }
        }
    }
}

void drum(int x, int y)
{
    int i,j,k,p1,p2;
    bool ok;ok=false;
    for(i=1; i<=x; i++)
     for(j=1; j<=y; j++)
     {
         ok=false;
         if(verif(i,j)==false)
         if(a[i][j]==b[i][j] && a[i][j]!=-1 && a[i][j]!=inf) {p1=i;p2=j;k=a[i][j];ok=true;}
         if(k<Min && ok==true) {Min=k;px=p1;py=p2;}
     }
}
int main()
{
    Min=9999;
   f>>N>>M;
   f.get();
   for(i=1; i<=N; i++)
   {
       f.getline(c,1000);
       k=strlen(c);
       for(j=0; j<k+1; j++)
       {
           if(c[j]=='X') {a[i][j+1]=-1;b[i][j+1]=-1;}
           else {a[i][j+1]=inf;b[i][j+1]=inf;}
           if(c[j]=='R') {xr=i;yr=j+1;a[i][j+1]=0;}
           if(c[j]=='J') {xj=i;yj=j+1;b[i][j+1]=0;}
       }

   }
   lee();
   lee1();
   drum(N,M);

   g<<Min+1<<' '<<px<<' '<<py;


    return 0;
}