Cod sursa(job #2206590)

Utilizator ScarymovieMocanu Alexandru Scarymovie Data 23 mai 2018 01:33:43
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.78 kb
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct punct
{
    int abs,ord;
};
bool Check(int x,int y,int n,int m)
{
    if(x<1) return false;
    if(y<1) return false;
    if(x>=n) return false;
    if(y>=m) return false;
    return true;
}
void ConstruiesteMatriceDistante(const punct& start, const vector<vector<bool> >& ma,vector<vector<int> >& dist)
{
    int dx[]= {-1,-1,-1,0,1,1,1,0},dy[]= {-1,0,1,1,1,0,-1,-1};
    queue<punct > coada;
    vector<vector<bool> > viz;
    dist.resize(ma.size());
    viz.resize(ma.size());
    for(int i=1; i<dist.size(); ++i)
    {
        dist[i].resize(ma[i].size(),-1);
        viz[i].resize(ma[i].size(),false);
    }
    coada.push(start);
    viz[start.abs][start.ord]=true;
    dist[start.abs][start.ord]=1;
    while(!coada.empty())
    {
        punct curr=coada.front();
        coada.pop();
        for(int i=0; i<8; ++i)
            if(Check(curr.abs+dx[i],curr.ord+dy[i],ma.size(),ma[1].size()) && !viz[curr.abs+dx[i]][curr.ord+dy[i]] && ma[curr.abs+dx[i]][curr.ord+dy[i]]==true)
            {
                dist[curr.abs+dx[i]][curr.ord+dy[i]]=dist[curr.abs][curr.ord]+1;
                viz[curr.abs+dx[i]][curr.ord+dy[i]]=true;
                coada.push({curr.abs+dx[i],curr.ord+dy[i]});
            }
    }
}
int main()
{
    ifstream fin("rj.in");
    ofstream fout("rj.out");
    punct romeo,julieta;
    int n,m;char s[102];
    vector<vector<bool> > mat;
    vector<vector<int> > dist1,dist2;
    fin>>n>>m;
    mat.resize(n+1);
    fin.get();
    for(int i=1; i<=n; ++i)
    {
        mat[i].resize(m+1);
        fin.getline(s,100);
        for(int j=1; j<=m; ++j)
        {
            if(s[j-1]=='R')
            {
                romeo.abs=i;
                romeo.ord=j;
                mat[i][j]=true;
                continue;
            }
            if(s[j-1]=='J')
            {
                julieta.abs=i;
                julieta.ord=j;
                mat[i][j]=true;
                continue;
            }
            if(s[j-1]==' ')
            {
                mat[i][j]=true;
                continue;
            }
            mat[i][j]=false;
        }
    }
    ConstruiesteMatriceDistante(romeo,mat,dist1);
    /*for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
            fout<<dist1[i][j]<<' ';
        fout<<'\n';
    }*/
    ConstruiesteMatriceDistante(julieta,mat,dist2);
    /*for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
            fout<<dist2[i][j]<<' ';
        fout<<'\n';
    }*/
    for(int i=1;i<mat.size();++i)
       for(int j=1;j<mat[i].size();++j)
            if(dist1[i][j]==dist2[i][j] && dist1[i][j]!=-1)
                {fout<<dist1[i][j]<<' '<<i<<' '<<j; break;}
    return 0;
}