Cod sursa(job #2470177)

Utilizator 1chiriacOctavian Neculau 1chiriac Data 8 octombrie 2019 20:17:22
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 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 mat[110][110])
{
	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]]==' ' && mat[linie+d1[ii]][coloana+d2[ii]]==0)
				chestie.push(make_pair(linie+d1[ii],coloana+d2[ii])),mat[linie+d1[ii]][coloana+d2[ii]]=mat[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(drumj);
	while(chestie.size()!=0)
		chestie.pop();
	chestie.push(make_pair(lr,cr));drumr[lr][cr]=1;
	bfs1(drumr);
	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;
		}
	fout<<minim<<" "<<rand<<" "<<coloana;
	return 0;
}