Cod sursa(job #1375048)

Utilizator mihaela_98Mihaela St mihaela_98 Data 5 martie 2015 11:51:13
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.32 kb
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int R[150][150],J[150][150];
int main()
{
    char M[150];
    int m,n,i,j,xr,yr,xj,yj,xx,yy,a,b,minim=32000;
    queue<int> qx;
    queue<int> qy;
    f>>m>>n;
    for(i=1;i<=m;i++)
    {
        f.get();
        f.get(M,150);
        for(j=1;j<=n;j++)
        {
            if(M[j-1]=='X') R[i][j]=J[i][j]=-2;
            if(M[j-1]==' ') R[i][j]=J[i][j]=-1;
            if(M[j-1]=='R') { xr=i; yr=j;}
            if(M[j-1]=='J') { xj=i; yj=j;}
        }
    }
    for(i=0;i<=n+1;i++)
    {
        R[0][i]=-4;
        R[m+1][i]=-4;
    }
    for(i=0;i<=n+1;i++)
    {
        J[0][i]=-4;
        J[m+1][i]=-4;
    }
    for(i=0;i<=m+1;i++)
    {
        R[i][0]=-4;
        R[i][n+1]=-4;
    }
    for(i=0;i<=m+1;i++)
    {
        J[i][0]=-4;
        J[i][n+1]=-4;
    }
    // Lee R
    qx.push(xr);
    qy.push(yr);
    while(qx.empty()!=true)
    {
        xx=qx.front();
        yy=qy.front();
        if(R[xx-1][yy]==-1 || R[xx-1][yy]>R[xx][yy]+1)
        {
            R[xx-1][yy]=R[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy);
        }
        if(R[xx+1][yy]==-1 || R[xx+1][yy]>R[xx][yy]+1)
        {
            R[xx+1][yy]=R[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy);
        }
        if(R[xx][yy-1]==-1 || R[xx][yy-1]>R[xx][yy]+1)
        {
            R[xx][yy-1]=R[xx][yy]+1;
            qx.push(xx);
            qy.push(yy-1);
        }
        if(R[xx][yy+1]==-1 || R[xx][yy+1]>R[xx][yy]+1)
        {
            R[xx][yy+1]=R[xx][yy]+1;
            qx.push(xx);
            qy.push(yy+1);
        }
        if(R[xx+1][yy+1]==-1 || R[xx+1][yy+1]>R[xx][yy]+1)
        {
            R[xx+1][yy+1]=R[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy+1);
        }
        if(R[xx-1][yy-1]==-1 || R[xx-1][yy-1]>R[xx][yy]+1)
        {
            R[xx-1][yy-1]=R[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy-1);
        }
        if(R[xx-1][yy+1]==-1 || R[xx-1][yy+1]>R[xx][yy]+1)
        {
            R[xx-1][yy+1]=R[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy+1);
        }
        if(R[xx+1][yy-1]==-1 || R[xx+1][yy-1]>R[xx][yy]+1)
        {
            R[xx+1][yy-1]=R[xx+1][yy]+1;
            qx.push(xx+1);
            qy.push(yy-1);
        }
        qx.pop();
        qy.pop();
    }
    // Lee J
    qx.push(xj);
    qy.push(yj);
    while(qx.empty()!=true)
    {
        xx=qx.front();
        yy=qy.front();
        if(J[xx-1][yy]==-1 || J[xx-1][yy]>J[xx][yy]+1)
        {
            J[xx-1][yy]=J[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy);
        }
        if(J[xx+1][yy]==-1 || J[xx+1][yy]>J[xx][yy]+1)
        {
            J[xx+1][yy]=J[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy);
        }
        if(J[xx][yy-1]==-1 || J[xx][yy-1]>J[xx][yy]+1)
        {
            J[xx][yy-1]=J[xx][yy]+1;
            qx.push(xx);
            qy.push(yy-1);
        }
        if(J[xx][yy+1]==-1 || J[xx][yy+1]>J[xx][yy]+1)
        {
            J[xx][yy+1]=J[xx][yy]+1;
            qx.push(xx);
            qy.push(yy+1);
        }
        if(J[xx+1][yy+1]==-1 || J[xx+1][yy+1]>J[xx][yy]+1)
        {
            J[xx+1][yy+1]=J[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy+1);
        }
        if(J[xx-1][yy-1]==-1 || J[xx-1][yy-1]>J[xx][yy]+1)
        {
            J[xx-1][yy-1]=J[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy-1);
        }
        if(J[xx-1][yy+1]==-1 || J[xx-1][yy+1]>J[xx][yy]+1)
        {
            J[xx-1][yy+1]=J[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy+1);
        }
        if(J[xx+1][yy-1]==-1 || J[xx+1][yy-1]>J[xx][yy]+1)
        {
            J[xx+1][yy-1]=J[xx+1][yy]+1;
            qx.push(xx+1);
            qy.push(yy-1);
        }
        qx.pop();
        qy.pop();
    }
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
           if(R[i][j]>0 && R[i][j]==J[i][j])
              if(R[i][j]<minim)
                 {
                     minim=R[i][j];
                     a=i;
                     b=j;
                 }
    g<<minim+1<<" "<<a<<" "<<b;
    f.close();
    g.close();
    return 0;
}