Cod sursa(job #1786978)

Utilizator pSergiuPatras Sergiu pSergiu Data 23 octombrie 2016 22:23:46
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
queue <pair <int,int> > romeo,julieta;
const int INF = 0x3f3f3f3f;
const int di[]={-1,-1,-1,0,1,1,1,0},
          dj[]={-1,0,1,1,1,0,-1,-1};
string text;
int n,m,i,j,iv,jv;
int ro[101][101],jul[101][101];
bool ok( int i, int j);
void traseur(int i, int j);
void traseuj(int i, int j);
void input();
void timpmin();
bool ok();
int main()
{
    input();
while(!romeo.empty())
{
    traseur(romeo.front().first, romeo.front().second);
    romeo.pop();
}
while(!julieta.empty())
{
    traseuj(julieta.front().first, julieta.front().second);
    julieta.pop();
}
int timp=INF,rezi,rezj;
for(i=1;i<=n;++i)
    for(j=1;j<=m;++j)
        if(ro[i][j] == jul[i][j] && ro[i][j] > 0 && ro[i][j] < timp)
        {
        timp = ro[i][j];
        rezi = i;
        rezj = j;
        }
fout<<timp<<" "<<rezi<<" "<<rezj;
fin.close();
fout.close();
    return 0;
}
void input()
{
    fin>>n>>m;
    getline(fin,text);
    for(int i=1;i<=n;i++)
        {
            getline(fin,text);
            for(int j=0;j<m;j++)
            {
                if(text[j]=='R')
                    {
                    ro[i][j+1]=1;
                    romeo.push({i,j+1});
                    }
                if(text[j]=='X')
                    {
                    ro[i][j+1] = -1;
                    jul[i][j+1] = -1;
                    }
                if(text[j]=='J')
                {
                    jul[i][j+1]=1;
                    julieta.push({i,j+1});
                }
            }
        }

}
void traseur(int i, int j)
{

    for(int d=0;d<=7;++d)
    {
        iv=i+di[d];
        jv=j+dj[d];
        if( ok(iv,jv) && (ro[iv][jv]>ro[i][j]+1 || ro[iv][jv]==0))
        {
            ro[iv][jv]=ro[i][j]+1;
            romeo.push({iv,jv});
        }
    }
}
void traseuj(int i, int j)
{
    for(int d=0;d<=7;++d)
    {
        iv=i+di[d];
        jv=j+dj[d];
        if(ok(iv,jv) && (jul[iv][jv]>jul[i][j]+1 || jul[iv][jv]==0))
        {
            jul[iv][jv]=jul[i][j]+1;
            julieta.push({iv,jv});
        }
    }
}
bool ok(int i, int j)
{
    if(ro[i][j] == -1) return false;
    else if(i < 1 || j < 1 || i>n || j > m) return false;
    return true;
}