Cod sursa(job #1372868)

Utilizator MaRryUuSManea Marius MaRryUuS Data 4 martie 2015 15:39:28
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.23 kb
#include <iostream>
#include<fstream>
#include<queue>
#include<string.h>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
queue <int> qx;
queue <int> qy;
char a[102][102];
char v[]="                                                                                                  .";
int b[102][102];
int main()
{
    int n,m,i,j,tmin=32000,tx,ty,x,y,xr,yr,xj,yj;
    f>>n>>m;
    f.get();
    for(i=1;i<=n;i++)
    {
        f.get(a[i],m+1);
        strcat(a[i],v);
        f.get();
    }
    for(i=1;i<=n;i++)
        for(j=0;j<m;j++)
            {
                if(a[i][j]==' ')b[i][j+1]=-1;
                    else if(a[i][j]=='X')b[i][j+1]=-2;
                            else if(a[i][j]=='R'){b[i][j+1]=0; xr=i; yr=j;}
                                    else if(a[i][j]=='J'){b[i][j+1]=0; xj=i; yj=j;}
            }
    for(i=0;i<=n+1;i++)
    {
        b[i][0]=-2;
        b[i][m+1]=-2;
    }
    for(i=0;i<=m+1;i++)
    {
        b[0][i]=-2;
        b[n+1][i]=-2;
    }
    qx.push(xr); qy.push(yr+1);
    while(qx.empty()!=true)
    {
        x=qx.front(); y=qy.front();
        if(b[x-1][y]==-1||b[x-1][y]>b[x][y]+1){b[x-1][y]=b[x][y]+1; qx.push(x-1); qy.push(y);}
        if(b[x-1][y+1]==-1||b[x-1][y+1]>b[x][y]+1){b[x-1][y+1]=b[x][y]+1; qx.push(x-1); qy.push(y+1);}
        if(b[x][y+1]==-1||b[x][y+1]>b[x][y]+1){b[x][y+1]=b[x][y]+1; qx.push(x); qy.push(y+1);}
        if(b[x+1][y+1]==-1||b[x+1][y+1]>b[x][y]+1){b[x+1][y+1]=b[x][y]+1; qx.push(x+1); qy.push(y+1);}
        if(b[x+1][y]==-1||b[x+1][y]>b[x][y]+1){b[x+1][y]=b[x][y]+1; qx.push(x+1); qy.push(y);}
        if(b[x+1][y-1]==-1||b[x+1][y-1]>b[x][y]+1){b[x+1][y-1]=b[x][y]+1; qx.push(x+1); qy.push(y-1);}
        if(b[x][y-1]==-1||b[x][y-1]>b[x][y]+1){b[x][y-1]=b[x][y]+1; qx.push(x); qy.push(y-1);}
        if(b[x-1][y-1]==-1||b[x-1][y-1]>b[x][y]+1){b[x-1][y-1]=b[x][y]+1; qx.push(x-1); qy.push(y-1);}
        qx.pop(); qy.pop();
    }
    qx.push(xj); qy.push(yj+1);
    while(qx.empty()!=true)
    {
        x=qx.front(); y=qy.front();
        i=x-1; j=y;
        if(b[x-1][y]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
                                            else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
                                                                        else if(i==tx)if(j<ty){tx=i;ty=j;}}}
            else if(b[x-1][y]>b[x][y]+1){b[x-1][y]=b[x][y]+1; qx.push(x-1); qy.push(y);}
        i=x-1; j=y+1;
        if(b[x-1][y+1]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
                                            else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
                                                                        else if(i==tx)if(j<ty){tx=i;ty=j;}}}
            else if(b[x-1][y+1]>b[x][y]+1){b[x-1][y+1]=b[x][y]+1; qx.push(x-1); qy.push(y+1);}
        i=x; j=y+1;
        if(b[x][y+1]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
                                            else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
                                                                        else if(i==tx)if(j<ty){tx=i;ty=j;}}}
            else if(b[x][y+1]>b[x][y]+1){b[x][y+1]=b[x][y]+1; qx.push(x); qy.push(y+1);}
        i=x+1; j=y+1;
        if(b[x+1][y+1]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
                                            else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
                                                                        else if(i==tx)if(j<ty){tx=i;ty=j;}}}
            else if(b[x+1][y+1]>b[x][y]+1){b[x+1][y+1]=b[x][y]+1; qx.push(x+1); qy.push(y+1);}
        i=x+1; j=y;
        if(b[x+1][y]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
                                            else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
                                                                        else if(i==tx)if(j<ty){tx=i;ty=j;}}}
            else if(b[x+1][y]>b[x][y]+1){b[x+1][y]=b[x][y]+1; qx.push(x+1); qy.push(y);}
        i=x+1; j=y-1;
        if(b[x+1][y-1]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
                                            else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
                                                                        else if(i==tx)if(j<ty){tx=i;ty=j;}}}
            else if(b[x+1][y-1]>b[x][y]+1){b[x+1][y-1]=b[x][y]+1; qx.push(x+1); qy.push(y-1);}
        i=x; j=y-1;
        if(b[x][y-1]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
                                            else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
                                                                        else if(i==tx)if(j<ty){tx=i;ty=j;}}}
            else if(b[x][y-1]>b[x][y]+1){b[x][y-1]=b[x][y]+1; qx.push(x); qy.push(y-1);}
        i=x-1; j=y-1;
        if(b[x-1][y-1]==b[x][y]+1){if(tmin>b[x][y]+1){tmin=b[x][y]+1; tx=i;ty=j;}
                                            else if(tmin==b[x][y]+1){if(i<tx){tx=i;ty=j;}
                                                                        else if(i==tx)if(j<ty){tx=i;ty=j;}}}
            else if(b[x-1][y-1]>b[x][y]+1){b[x-1][y-1]=b[x][y]+1; qx.push(x-1); qy.push(y-1);}
        qx.pop(); qy.pop();
    }
    g<<tmin+1<<" "<<tx<<" "<<ty;
    return 0;
}