Cod sursa(job #2470368)

Utilizator 1chiriacOctavian Neculau 1chiriac Data 9 octombrie 2019 09:12:33
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <fstream>
#include <queue>
#include <iostream>
#include <cstring>
using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
queue < pair <int,int> > chestie;
char harta[110][110],c;int n,m,lr,cr,lj,cj,drumr[110][110],drumj[110][110],d1[10]={-1,0,1,0,-1,-1,1,1},d2[10]={0,1,0,-1,-1,1,1,-1},i,j,ii;
void bordare_mat ()
{
    for(i=1;i<=n;++i)
        strcpy(harta[i]+1,harta[i]);
	for(i=0;i<=n+1;++i)
		harta[i][0]='X',harta[i][m+1]='X';
	for(i=0;i<=m+1;++i)
		harta[0][i]='X',harta[n+1][i]='X';
}
void bfs1 ()
{
	int linie,coloana;
	while(chestie.size()!=0)
	{
		linie=chestie.front().first;coloana=chestie.front().second;
		for(ii=0;ii<8;++ii)
			if(harta[linie+d1[ii]][coloana+d2[ii]]==' ' && (drumj[linie+d1[ii]][coloana+d2[ii]]==0 || drumj[linie+d1[ii]][coloana+d2[ii]]>drumj[linie][coloana]+1))
				chestie.push(make_pair(linie+d1[ii],coloana+d2[ii])),drumj[linie+d1[ii]][coloana+d2[ii]]=drumj[linie][coloana]+1;
        chestie.pop();
	}

}
void bfs2 ()
{
	int linie,coloana;
	while(chestie.size()!=0)
	{
		linie=chestie.front().first;coloana=chestie.front().second;
		for(ii=0;ii<8;++ii)
			if(harta[linie+d1[ii]][coloana+d2[ii]]==' ' && (drumr[linie+d1[ii]][coloana+d2[ii]]==0 || drumr[linie+d1[ii]][coloana+d2[ii]]>drumr[linie][coloana]+1) )
				chestie.push(make_pair(linie+d1[ii],coloana+d2[ii])),drumr[linie+d1[ii]][coloana+d2[ii]]=drumr[linie][coloana]+1;
        chestie.pop();
	}

}
int main ()
{
	int rand,coloana,minim=2000000000;
	fin>>n>>m;//fin>>c;
	for(i=0;i<=n;++i)
        fin.getline(harta[i],m+3);
    bordare_mat();
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
        {
            if(harta[i][j]=='R')
                lr=i,cr=j;
            else if(harta[i][j]=='J')
                lj=i,cj=j;
        }
	chestie.push(make_pair(lj,cj));drumj[lj][cj]=1;
	bfs1();
	while(chestie.size()!=0)
		chestie.pop();
	chestie.push(make_pair(lr,cr));drumr[lr][cr]=1;
	bfs2();
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
		{
			if(drumj[i][j]==drumr[i][j] && drumj[i][j]<minim && drumr[i][j]!=0)
				minim=drumj[i][j],rand=i,coloana=j;
			else if(drumr[i][j]==drumj[i][j] && drumj[i][j]==minim && j<coloana)
				rand=i,coloana=j;
		}
	fout<<minim<<" "<<rand<<" "<<coloana<<"\n";
	/*for(i=1;i<=n;++i)
	{
		for(j=1;j<=m;++j)
			fout<<drumj[i][j]<<" ";
		fout<<"\n";
	}
	fout<<"\n";
	for(i=1;i<=n;++i)
	{
		for(j=1;j<=m;++j)
			fout<<drumr[i][j]<<" ";
		fout<<"\n";
	}*/
	return 0;
}