Cod sursa(job #2999389)

Utilizator NIIN100Nistor Nichita NIIN100 Data 10 martie 2023 22:16:37
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <iostream>
#include <fstream>

using namespace std;

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

struct coada
{
	short l;
	short c;
	int nr;
} coada[10001];

int rom[102][102], jul[101][101];

int main()
{
	short n, m, lr, cr, lj, cj, lc, cc, vl[8]={0, 1, 0, -1, -1, -1, 1, 1}, vc[8]={-1, 0, 1, 0, -1, 1, -1, 1}, aux, lf, cf;
	char c;
	int inc, sf, mini=100001;

	in>>n>>m;
	for(int i=0; i<=n+1; i++)
	{
		rom[i][0]=-1;
		jul[i][0]=-1;
	}
	for(int i=0; i<=m+1; i++)
	{
		rom[0][i]=-1;
		jul[0][i]=-1;
	}
	for(int i=0; i<=n+1; i++)
	{
		rom[i][m+1]=-1;
		jul[i][m+1]=-1;
	}
	for(int i=0; i<=m+1; i++)
	{
		rom[n+1][i]=-1;
		jul[n+1][i]=-1;
	}
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
		{
			in.get(c);
			if(c=='\n')
				in.get(c);
			if(c=='X')
			{
				rom[i][j]=-1;
				jul[i][j]=-1;
			}
			else if(c=='R')
			{
				lr=i;
				cr=j;
			}
			else if(c=='J')
			{
				lj=i;
				cj=j;
			}
		}

	inc=1;
	sf=1;
	coada[1].l=lr;
	coada[1].c=cr;
	coada[1].nr=1;
	rom[lr][cr]=1;
	while(inc<=sf)
	{
		lc=coada[inc].l;
		cc=coada[inc].c;
		for(aux=0; aux<8; aux++)
			if(rom[lc+vl[aux]][cc+vc[aux]]==0)
			{
				coada[++sf].l=lc+vl[aux];
				coada[sf].c=cc+vc[aux];
				coada[sf].nr=coada[inc].nr+1;
				rom[lc+vl[aux]][cc+vc[aux]]=coada[inc].nr+1;
			}
		inc++;
	}

	inc=1;
	sf=1;
	coada[1].l=lj;
	coada[1].c=cj;
	coada[1].nr=1;
	jul[lj][cj]=1;
	while(inc<=sf)
	{
		lc=coada[inc].l;
		cc=coada[inc].c;
		for(aux=0; aux<8; aux++)
			if(jul[lc+vl[aux]][cc+vc[aux]]==0)
			{
				coada[++sf].l=lc+vl[aux];
				coada[sf].c=cc+vc[aux];
				coada[sf].nr=coada[inc].nr+1;
				jul[lc+vl[aux]][cc+vc[aux]]=coada[inc].nr+1;
			}
		inc++;
	}

	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			if(rom[i][j]==jul[i][j] and rom[i][j]!=-1 and rom[i][j]!=0 and rom[i][j]<mini)
			{
				lf=i;
				cf=j;
				mini=rom[i][j];
			}

	out<<mini<<" "<<lf<<" "<<cf;

    return 0;
}