Cod sursa(job #2165628)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 13 martie 2018 12:54:51
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>

using namespace std;

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

struct poz
{
    int l, c;
};
queue<poz>coada;
int dx[]={-1, -1, 0, 1, 1, 1, 0, -1};
int dy[]={0, 1, 1, 1, 0, -1, -1, -1};

char a[101][101];
int romeo[101][101], julieta[101][101];
int n, m, xr, yr, xj, yj;
char ch;

void lee(int x, int y, int nr[101][101])
{
    poz p, q;
    int lv, cv;
    p.l=x; p.c=y;
    coada.push(p);
    nr[x][y]=1;
    while(!coada.empty())
    {
        p=coada.front();
        coada.pop();
        for(int d=0; d<=7; ++d)
        {
            lv=p.l+dx[d];
            cv=p.c+dy[d];
            if(lv>0 && lv<=n && cv>0 && cv<=m)
            {
                if(a[lv][cv]==' ' && nr[lv][cv]>nr[p.l][p.c]+1)
                {
                    nr[lv][cv]=nr[p.l][p.c]+1;
                    q.l=lv; q.c=cv;
                    coada.push(q);
                }
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    fin.get();
    for(int i=1; i<=n; ++i)
    {
        fin.getline(a[i]+1, 101);
        for(int j=1; j<=m; ++j)
        {
            if(a[i][j]=='R')
            {
                a[i][j]=' ';
                xr=i; yr=j;
            }
            else if(a[i][j]=='J')
            {
                a[i][j]=' ';
                xj=i; yj=j;
            }
        }
    }
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
        {
            romeo[i][j]=INT_MAX;
            julieta[i][j]=INT_MAX;
        }
    }
    lee(xr, yr, romeo);
    lee(xj, yj, julieta);
    int sol=INT_MAX, l, c;
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
        {
            if(romeo[i][j]==julieta[i][j] && romeo[i][j]<sol)
            {
                sol=romeo[i][j];
                l=i; c=j;
            }
        }
    }
    fout<<sol<<" "<<l<<" "<<c<<"\n";
    return 0;
}