Cod sursa(job #1721486)

Utilizator leraValeria lera Data 25 iunie 2016 18:52:02
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <iostream>
#include <fstream>
#include <queue>
#define pii pair<int,int>
#define x first
#define y second
#include <string>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
queue<pair<int,int> >jul;
queue<pair<int,int> >rom;
pair<int,int>p;
int a[101][101],b[101][101];
int dx[]={-1,-1,-1,0,0,1,1,1};
int dy[]={-1,0,1,-1,1,-1,0,1};
int n,ok=0,c1,c2,tmin,nr;
unsigned int m;
int ins(int i,unsigned int j)
{
    if(i<=n && i>=1 && j<=m && j>=1)
        return 1;
    return 0;
}
void vecinirom(int l,int col)
{
    for(int d=0;d<=7;d++)
    {
        int ii=l+dx[d];
        int jj=col+dy[d];
        if(ins(ii,jj) && a[ii][jj]==0)
        {
            rom.push(make_pair(ii,jj));
            a[ii][jj]=a[l][col]+1;
        }
    }
}
void vecinijul(int l,int col)
{
    for(int d=0;d<=7;d++)
    {
        int ii=l+dx[d];
        int jj=col+dy[d];
        if(ins(ii,jj) && b[ii][jj]==0)
        {
            jul.push(make_pair(ii,jj));
            b[ii][jj]=b[l][col]+1;
        }
        if(ins(ii,jj) && a[ii][jj]==b[ii][jj] && a[ii][jj]==nr)
            {ok=1;

            tmin=b[ii][jj];
            c1=ii;
            c2=jj;  break;
            }
    }
}

int main()
{
    int i=0;
    unsigned int j;
    fin>>n>>m;
    while(!fin.eof())
    {
        string s;
        getline(fin,s);
        for(j=0;j<=s.size();++j)
            {
                if(s[j]=='R')
                    {
                        a[i][j+1]=1;
                        rom.push(make_pair(i,j+1));
                    }
                if(s[j]=='J')
                {
                    b[i][j+1]=1;
                    jul.push(make_pair(i,j+1));
                }
                if(s[j]=='X')
                        a[i][j+1]=b[i][j+1]=-1;
            }
        i++;
    }
    nr=2;
    while(ok==0)
    {

        pii p=rom.front();
        while(a[p.x][p.y]+1==nr && !rom.empty())
        {
            vecinirom(p.x,p.y);
            rom.pop();
              p=rom.front();
        }
        p=jul.front();
        while(b[p.x][p.y]+1==nr && ok==0)
        {
            vecinijul(p.x,p.y);
            jul.pop();
              p=jul.front();
        }
        nr++;
    }
    fout<<tmin<<" "<<c1<<" "<<c2;
    return 0;
}