Cod sursa(job #2952459)

Utilizator panterasbook29Turcu Stiolica Alexandru panterasbook29 Data 9 decembrie 2022 11:56:25
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
#include <string.h>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

int a[101][101],b[101][101];
int i,n,m,j,cr1,cr2,cj1,cj2, z1[9]={0,-1,-1,-1,0,1,1,1,0}, z2[9]={0,-1,0,1,1,1,0,-1,-1},p,u,x1,x2,y1,y2,xcautat,ycautat,timpc,h;
char s[101],q;

struct t1
{
    int c1,c2;
} t1[10001];
struct t2
{
    int c1,c2;
} t2[10001];

int main()
{
    fin>>n>>m>>noskipws>>q>>skipws;
    for(i=1;i<=n;i++)
    {
        fin.getline(s,101);
        h=strlen(s)-1;
        for(j=0;j<=h;j++)
        {
            if(s[j]=='X')
            {
                a[i][j+1]=-1;
                b[i][j+1]=-1;
            }
            if(s[j]=='R')
            {
                cr1=i; cr2=j+1;
            }
            else if(s[j]=='J')
            {
                cj1=i; cj2=j+1;
            }
        }
    }
    for(i=0;i<=n+1;i++)
    {
        a[i][0]=-1;
        a[i][m+1]=-1;
        b[i][0]=-1;
        b[i][m+1]=-1;
    }
    for(i=0;i<=m+1;i++)
    {
        a[0][i]=-1;
        a[n+1][i]=-1;
        b[0][i]=-1;
        b[n+1][i]=-1;
    }

    p=1; u=1; t1[1].c1=cr1; t1[1].c2=cr2;

    while(p<=u)
    {
        x1=t1[p].c1; y1=t1[p].c2;
        for(i=1;i<=8;i++)
        {
            x2=x1+z1[i]; y2=y1+z2[i];
            if(a[x2][y2]==0 || (a[x2][y2]>a[x1][y1]+1 && a[x2][y2]!=-1))
            {
                a[x2][y2]=a[x1][y1]+1;
                u++;
                t1[u].c1=x2; t1[u].c2=y2;
            }
        }
        p++;
        if(u>=10000)
            break;
    }
    p=1; u=1; t1[1].c1=cj1; t1[1].c2=cj2;
    while(p<=u)
    {
        x1=t1[p].c1; y1=t1[p].c2;
        for(i=1;i<=8;i++)
        {
            x2=x1+z1[i]; y2=y1+z2[i];
            if(b[x2][y2]==0 || (b[x2][y2]>b[x1][y1]+1 && b[x2][y2]!=-1))
            {
                b[x2][y2]=b[x1][y1]+1;
                u++;
                t1[u].c1=x2; t1[u].c2=y2;
            }
        }
        p++;
        if(u>=10000)
            break;
    }

    int minim=99999999,timp=99999999;

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            timpc=-1;
            if(a[i][j]==b[i][j])
                    timpc=a[i][j];
            if(a[i][j]>0 && b[i][j]>0 && timpc>-1 && timpc<timp)
            {
                xcautat=i; ycautat=j;
                timp=timpc;
            }
        }
    }
    fout<<timp+1<<" "<<xcautat<<" "<<ycautat;

    return 0;
}