Cod sursa(job #1501177)

Utilizator vancea.catalincatalin vancea.catalin Data 13 octombrie 2015 00:50:30
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstring>
#define VM 999999999
#define LM 2155
using namespace std;
fstream fin("rj.in",ios::in),fout("rj.out",ios::out);
struct d{int i,j;};d x[999999];
int di[]={-1,-1,0,1,1,1,0,-1},dj[]={0,1,1,1,0,-1,-1,-1},mr[LM][LM],mj[LM][LM],n,m,pri,prj,pji,pjj;
char c[LM][LM];
void bfs(int start,int stop,int aux[LM][LM])
{
    int k,a,b;
    while(start<=stop)
    {
        for(k=0;k<8;k++)
        {
            a=x[start].i+di[k];
            b=x[start].j+dj[k];
            if(aux[a][b]==0&&c[a][b]!='X')
            {
                aux[a][b]=aux[x[start].i][x[start].j]+1;
                x[++stop]={a,b};
            }
        }
        start++;
    }
}
void det()
{
    int i,j,lmin,cmin,minim=VM;
    lmin=cmin=LM;
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(mr[i][j]==mj[i][j]&&mr[i][j]!=0&&mr[i][j]<minim)
            {
                minim=mr[i][j];
                lmin=i;
                cmin=j;
            }
        }
    }
    fout<<lmin+1<<" "<<cmin+1<<"\n";
}
int main()
{
    int i,j;
    fin>>n>>m;
    fin.getline(c[1],LM);
    for(i=0;i<n;i++)
    {
        fin.getline(c[i],LM);
        if(strchr(c[i],'R'))
        {
            pri=i;prj=strchr(c[i],'R')-c[i];
        }
        if(strchr(c[i],'J'))
        {
            pji=i;pjj=strchr(c[i],'J')-c[i];
        }
    }
    for(i=-1;i<=n;i++)c[i][-1]=c[i][m]='X';
    for(j=-1;j<=m;j++)c[-1][j]=c[n][j]='X';
    x[1]={pri,prj};mr[pri][prj]=1;
    bfs(1,1,mr);
    x[1]={pji,pjj};mj[pji][pjj]=1;
    bfs(1,1,mj);
    fout<<mr[pji][pjj]/2+1<<" ";
    det();
    return 0;
}