Cod sursa(job #1576914)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 22 ianuarie 2016 22:55:14
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.27 kb
#include <fstream>
#include <cstring>
#include <queue>
#define NM 105

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

const int dl[9]={0, -1, -1, -1, 0, 0, 1, 1, 1};
const int dc[9]={0, -1, 0, 1, -1, 1, -1, 0, 1};

struct pozitie
{
    int l;
    int c;
};

pozitie poz, poz2;

int N, M, i, j, a;
int pasi[NM][NM];
int pasi2[NM][NM];
int l1, c1, l2, c2;
int lin, col, mn;
char s[NM];
queue<pozitie> q, q2;

int main()
{
    fin >> N >> M;
    fin.get();
    for (i=1; i<=N; i++)
    {
        fin.get(s, NM);
        fin.get();
        for (j=0; j<M; j++)
        {
            if (s[j]=='R')
            {
                l1=i;
                c1=j+1;
            }
            if (s[j]=='J')
            {
                l2=i;
                c2=j+1;
            }
            if (s[j]=='X')
            {
                pasi[i][j+1]=-1;
                pasi2[i][j+1]=-1;
            }
        }
    }
    for (i=0; i<=M+1; i++)
    {
        pasi[0][i]=-1;
        pasi[N+1][i]=-1;
        pasi2[0][i]=-1;
        pasi2[N+1][i]=-1;
    }
    for (i=0; i<=N+1; i++)
    {
        pasi[i][0]=-1;
        pasi[i][M+1]=-1;
        pasi2[i][0]=-1;
        pasi2[i][M+1]=-1;
    }
    poz.l=l1;
    poz.c=c1;
    q.push(poz);
    pasi[l1][c1]=1;
    while (q.empty()==false)
    {
        poz=q.front();
        q.pop();
        for (i=1; i<=8; i++)
        {
            poz2.l=poz.l+dl[i];
            poz2.c=poz.c+dc[i];
            if (pasi[poz2.l][poz2.c]>-1)
            {
                if (pasi[poz2.l][poz2.c]==0)
                {
                    pasi[poz2.l][poz2.c]=pasi[poz.l][poz.c]+1;
                    q.push(poz2);
                }
                else
                {
                    a=pasi[poz2.l][poz2.c];
                    pasi[poz2.l][poz2.c]=min(pasi[poz2.l][poz2.c], pasi[poz.l][poz.c]+1);
                    if (a>pasi[poz2.l][poz2.c])
                      q.push(poz2);
                }
            }
        }
    }
    poz.l=l2;
    poz.c=c2;
    q2.push(poz);
    pasi2[l2][c2]=1;
    while (q2.empty()==false)
    {
        poz=q2.front();
        q2.pop();
        for (i=1; i<=8; i++)
        {
            poz2.l=poz.l+dl[i];
            poz2.c=poz.c+dc[i];
            if (pasi2[poz2.l][poz2.c]>-1)
            {
                if (pasi2[poz2.l][poz2.c]==0)
                {
                    pasi2[poz2.l][poz2.c]=pasi2[poz.l][poz.c]+1;
                    q2.push(poz2);
                }
                else
                {
                    a=pasi2[poz2.l][poz2.c];
                    pasi2[poz2.l][poz2.c]=min(pasi2[poz2.l][poz2.c], pasi2[poz.l][poz.c]+1);
                    if (a>pasi2[poz2.l][poz2.c])
                      q2.push(poz2);
                }
            }
        }
    }
    mn=2000000000;
    for (i=1; i<=N; i++)
    {
        for (j=1; j<=M; j++)
        {
            if (pasi[i][j]<mn && pasi[i][j]>0 && pasi[i][j]==pasi2[i][j] && pasi2[i][j]<mn && pasi2[i][j]>0)
            {
                mn=pasi[i][j];
                lin=i;
                col=j;
            }
        }
    }
    fout << mn << " " << lin << " " << col << '\n';
    fin.close();
    fout.close();
    return 0;
}