Cod sursa(job #2154515)

Utilizator cristinahalmageanHalmagean Cristina cristinahalmagean Data 6 martie 2018 23:45:57
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
char a[100][100],s[100];
int i,j,n,m,startx[4],starty[4],x,y,i_urmator,j_urmator,p=1,ok;
queue<pair<int,int> >coada;
int di[]={0,-1,-1,-1,0,0,1,1,1};
int dj[]={0,-1,0,1,-1,1,-1,0,1};
struct
{
   int nr,d;
}v[100][100];
bool OK(int i,int j)
{
    if(i<1||j<1||i>n||j>m)
        return false;
    if(v[i][j].nr==-1)
        return false;
    return true;
}
int main()
{
    f>>n>>m;int pi=n+1;int pj=m+1;int l=n*m+1;
    for(i=1;i<=n;i++)
    {
        f.get();
        f.get(s,100);
        strcpy(a[i],s);
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(a[i][j]==' ')
                v[i][j+1].nr=n*m;
            if(a[i][j]=='X')
                v[i][j+1].nr=-1;
            if(a[i][j]=='R'||a[i][j]=='J')
            {
                v[i][j+1].nr=1;
                startx[p]=i;
                starty[p]=j+1;
                p++;
            }
        }
    }
    i=1;
        coada.push(make_pair(startx[i],starty[i]));
    while(!coada.empty())
    {
        x=coada.front().first;
        y=coada.front().second;
        v[x][y].d=1;
        coada.pop();
        for(int dir=1;dir<=8;dir++)
        {
            i_urmator=x+di[dir];
            j_urmator=y+dj[dir];
            if(OK(i_urmator,j_urmator)&&v[i_urmator][j_urmator].nr>v[x][y].nr+1)
            {
                v[i_urmator][j_urmator].nr=v[x][y].nr+1;
                v[i_urmator][j_urmator].d=1;
                coada.push(make_pair(i_urmator,j_urmator));
            }
    }}
    i=2;
    coada.push(make_pair(startx[i],starty[i]));
    while(!coada.empty())
    {
        x=coada.front().first;
        y=coada.front().second;
        v[x][y].d=2;
        coada.pop();
        for(int dir=1;dir<=8;dir++)
        {
            i_urmator=x+di[dir];
            j_urmator=y+dj[dir];
            if(OK(i_urmator,j_urmator)&&v[i_urmator][j_urmator].nr>v[x][y].nr+1)
            {
                v[i_urmator][j_urmator].nr=v[x][y].nr+1;
                v[i_urmator][j_urmator].d=2;
                coada.push(make_pair(i_urmator,j_urmator));
            }
            else if(OK(i_urmator,j_urmator)&&v[i_urmator][j_urmator].nr==v[x][y].nr+1&&v[i_urmator][j_urmator].d!=v[x][y].d)
            {
                if(v[i_urmator][j_urmator].nr<l)
                {
                    l=v[x][y].nr+1;
                    pi=i_urmator;
                    pj=j_urmator;
                }
                if(v[i_urmator][j_urmator].nr==l)
                {
                    if(i_urmator<pi)
                    {
                        pi=i_urmator;
                        pj=j_urmator;
                    }
                    if(i_urmator==pi)
                    {
                        if(j_urmator<pj)
                            pj=j_urmator;
                    }
                }
                coada.push(make_pair(i_urmator,j_urmator));
            }
    }}
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        g<<v[i][j].nr<<" ";
        g<<"\n";
    }
    g<<l<<" "<<pi<<" "<<pj;
 return 0;
}