Cod sursa(job #1751998)

Utilizator Fanika123Tanasa Stefan Fanika123 Data 2 septembrie 2016 15:16:21
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <bits/stdc++.h>
#define oo 1000000
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,m,xr,yr,xj,yj,dr[105][105],dj[105][105];
char a[105][105];
int dx[]={0,0,-1,1,-1,1,-1,1};
int dy[]={-1,1,0,0,-1,1,1,-1};
queue <pair<int,int> > q;
void Citire()
{
    int i,j;
    fin>>n>>m;
    fin.get();
    for (i=1;i<=n;i++)
    {
        fin.getline(a[i]+1,105);
        for (j=1;j<=m;j++)
            if (a[i][j]=='R')
            {
                xr=i;
                yr=j;
            }
            else if (a[i][j]=='J')
            {
                xj=i;
                yj=j;
            }
    }
}

void Bordare()
{
    int i;
    for (i=0;i<=m+1;i++) a[0][i]=a[n+1][i]='X';
    for (i=0;i<=n+1;i++) a[i][0]=a[i][m+1]='X';

}
void Init()
{
    int i,j;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            dj[i][j]=dr[i][j]=oo;
}
void Lee_R()
{
    int i,j,x,y,k;
    q.push(make_pair(xr,yr));
    dr[xr][yr]=1;
    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for (k=0;k<8;k++)
        {
            x=i+dx[k];
            y=j+dy[k];
            if (dr[x][y]>dr[i][j]+1 && a[x][y]!='X')
            {
                dr[x][y]=dr[i][j]+1;
                q.push(make_pair(x,y));
            }
        }
    }
}
void Lee_J()
{
    int i,j,x,y,k;
    q.push(make_pair(xj,yj));
    dj[xj][yj]=1;
    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for (k=0;k<8;k++)
        {
            x=i+dx[k];
            y=j+dy[k];
            if (dj[x][y]>dj[i][j]+1 && a[x][y]!='X')
            {
                dj[x][y]=dj[i][j]+1;
                q.push(make_pair(x,y));
            }
        }
    }
}
void Intalnire()
{
    int i,j,mini,poz1,poz2;
    mini=oo;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(dr[i][j]==dj[i][j] && mini>dr[i][j])
            {
                mini=dr[i][j];
                poz1=i;
                poz2=j;
            }
    fout<<mini<<" "<<poz1<<" "<<poz2<<"\n";
}
int main()
{
    Citire();
    Bordare();
    Init();
    Lee_R();
    Lee_J();
    Intalnire();
    fin.close();
    fout.close();
    return 0;
}