Cod sursa(job #1796529)

Utilizator CriistinaMicula Cristina Criistina Data 3 noiembrie 2016 16:11:36
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 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;
    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)
            {
                g<<romeo[i][j]<<" "<<i<<" "<<j;
                ok=1;
            }
    return 0;
}