Cod sursa(job #1796606)

Utilizator CriistinaMicula Cristina Criistina Data 3 noiembrie 2016 17:07:19
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <string>

using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");

string s[101];
int n, m;
int viz [101][101];
int dx[8]={-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8]={-1, 0, 1, -1, 1, -1, 0, 1};
typedef pair<int, int> pereche;

bool inside(int x, int y)
{
    if(x<=0 || x>n || y<=0 || y>m)
        return false;
    return true;
}
void lee(pereche a, pereche b, int mr[101][101])
{
    queue< pair<pereche, int> > c;
    pair <pereche, int> x;
    x=make_pair(a, 1);
    c.push(x);
    int  ok=0;
    int ii, jj, nr;
    while(!c.empty() && ok==0)
    {
        nr=c.front().second+1;
        for(int i=0;i<8 && ok==0;i++)
        {
            ii=c.front().first.first +dx[i];
            jj=c.front().first.second+dy[i];
            if(inside(ii, jj) && viz[ii][jj]==0 && !(ii==a.first && jj==a.second))
            {
                x=make_pair(make_pair(ii, jj), nr);
                c.push(x);
                mr[ii][jj]=nr;
                viz[ii][jj]=1;
            }
            if(ii==b.first && jj==b.second)
                return;
        }
        c.pop();
    }
}
int main()
{
    pair<int,int> rm, jl;
    int romeo[101][101], julieta[101][101];
    f>>n>>m;
    f.get();
    for(int i=0;i<n;i++)
        getline(f, s[i]);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
        {
            if(s[i][j]=='R')
            {
                rm.first=i+1;
                rm.second=j+1;
            }
            if(s[i][j]=='J')
            {
                jl.first=i+1;
                jl.second=j+1;
            }
            if(s[i][j]=='X')
                viz[i+1][j+1]=-1;
        }
    }
    lee(rm, jl, romeo);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(viz[i][j]!=-1)
                viz[i][j]=0;
    lee(jl, rm, julieta);
    int ok=0;
    pair<pereche, int> x;
    x=make_pair(make_pair(0, 0), n*m);
    for(int i=1;i<=n && ok==0;i++)
        for(int j=1;j<=m && ok==0;j++)
            if(romeo[i][j]==julieta[i][j] && romeo[i][j]!=0)
            {
                if(romeo[i][j]<x.second)
                {
                    x.second=romeo[i][j];
                    x.first.first=i;
                    x.first.second=j;
                }
            }
    g<<x.second<<" "<<x.first.first<<" "<<x.first.second;
    return 0;
}