Cod sursa(job #3138472)

Utilizator rarest@yahoo.comtorcea rares [email protected] Data 19 iunie 2023 19:00:15
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,m;
int a[101][101];
int rom[101][101];
int jul[101][101];
int di[]={-1,0,1,0,1,1,-1,-1};
int dj[]={0,1,0,-1,1,-1,1,-1};
int x[10001];
int y[10001];
int traseu[101][101];

bool inmat(int i,int j)
{
    return i<=n && i>=1 && j>=1 && j<=m;
}

void lee1(int a[101][101],int x1,int y1)
{
    int p=1,u=1;
    int i,j;
    int ii,ij;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            traseu[i][j]=0;

    traseu[x1][y1]=1;
    rom[x1][y1]=1;
    x[1]=x1;
    y[1]=y1;
    while(p<=u)
    {
        i=x[p];
        j=y[p];
        int k;
        for(k=0;k<8;k++)
        {
            ii=i+di[k];
            ij=j+dj[k];
            if(inmat(ii,ij) && a[ii][ij]!=1 && traseu[ii][ij]==0)
            {
                u++;
                x[u]=ii;
                y[u]=ij;
                traseu[ii][ij]=traseu[i][j]+1;
                rom[ii][ij]=traseu[ii][ij];
            }
        }
        p++;
    }
}

void lee2(int a[101][101],int x1,int y1)
{
    int p=1,u=1;
    int i,j;
    int ii,ij;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            traseu[i][j]=0;

    traseu[x1][y1]=1;
    jul[x1][y1]=1;
    x[1]=x1;
    y[1]=y1;
    while(p<=u)
    {
        i=x[p];
        j=y[p];
        int k;
        for(k=0;k<8;k++)
        {
            ii=i+di[k];
            ij=j+dj[k];
            if(inmat(ii,ij) && a[ii][ij]!=1 && traseu[ii][ij]==0)
            {
                u++;
                x[u]=ii;
                y[u]=ij;
                traseu[ii][ij]=traseu[i][j]+1;
                jul[ii][ij]=traseu[ii][ij];
            }
        }
        p++;
    }
}

int main()
{
    f>>n>>m;
    int i,j;
    char ch;
    int x1,y1,x2,y2;
    for(i=1;i<=n;i++)
    {
        f.get();
        for(j=1;j<=m;j++)
        {
            f.get(ch);
            if(ch==' ')
                a[i][j]=0;
            else
                if(ch=='X')
                a[i][j]=1;
            else
                if(ch=='R')
                {
                    a[i][j]=2;
                    x1=i;
                    y1=j;
                }
            else
            {
                a[i][j]=3;
                x2=i;
                y2=j;
            }
        }
    }

    lee1(a,x1,y1);
    lee2(a,x2,y2);

    int lin,col;
    lin=0,col=0;
    int minim=1e10;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(rom[i][j]==jul[i][j] && a[i][j]!=1 && rom[i][j]>0 && jul[i][j]>0)
            {
                if(minim>rom[i][j])
                {
                    minim=rom[i][j];
                    lin=i;
                    col=j;
                }
            }
        }
    }

    g<<minim<<" "<<lin<<" "<<col;
    return 0;
}