Cod sursa(job #1003298)

Utilizator cristigrigoreGrigore Cristan Andrei cristigrigore Data 30 septembrie 2013 11:57:54
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
#include <cstring>
#define inf 10000
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
unsigned char Q[1001][2];

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,nr,xx,yy,x,y,st,dr;
    bool ok;
    ok=true;
    Q[0][0]=xr;Q[0][1]=yr;
    st=0;dr=0;
    while(ok==true && st<=dr)
    {

        x=Q[st][0], y=Q[dr][1];
        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;
                Q[++dr][0]=xx;
                Q[dr][1]=yy;
                 if(xx=xj && yy==yj) ok=false;
            }
        }st++;
    }
}
void lee1()

{
    int i,nr,xx,yy,x,y,st,dr;
    bool ok;
    ok=true;
    Q[0][0]=xj;Q[0][1]=yj;
    st=0;dr=0;
    while(ok==true && st<=dr)
    {

        x=Q[st][0], y=Q[dr][1];
        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;
                Q[++dr][0]=xx;
                Q[dr][1]=yy;
                if(xx=xr && yy==yr) ok=false;
            }
        }st++;
    }
}
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;
}