Cod sursa(job #2580138)

Utilizator 1chiriacOctavian Neculau 1chiriac Data 13 martie 2020 12:51:23
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
int n,m,dp[3][1005][1005],d1[]={-1,0,1,0},d2[]={0,1,0,-1},lin,col;char harta[1005][1005];
queue < pair <int,int> > chestie;
bool bun (int l, int c) {
	if(l>0 && l<=n && c>0 && c<=m && harta[l][c]==' ')
		return true;
	return false;
}
void lee (int nr) {
	while(!chestie.empty()) {
		lin=chestie.front().first;col=chestie.front().second;chestie.pop();
		for(int i=0;i<4;++i)
			if(bun(lin+d1[i],col+d2[i])==true && dp[nr][lin+d1[i]][col+d2[i]]==0) {
				dp[nr][lin+d1[i]][col+d2[i]]=dp[nr][lin][col]+1;
				chestie.push({lin+d1[i],col+d2[i]});
			}
	}
}
int main () {
	int l1,c1,l2,c2,ans=1e9;
	fin>>n>>m;fin.getline(harta[1],10);
	for(int i=1;i<=n;++i)
		fin.getline(harta[i]+1,m+5);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(harta[i][j]=='R')
				l1=i,c1=j;
			else if (harta[i][j]=='J')
				l2=i,c2=j;
	chestie.push({l1,c1});dp[0][l1][c1]=1;lee(0);chestie.push({l2,c2});dp[1][l2][c2]=1;lee(1);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(dp[0][i][j]==dp[1][i][j] && dp[0][i][j]!=0 && dp[0][i][j]<ans) {
				ans=dp[0][i][j];l1=i;l2=j;
			}
	fout<<ans-1<<" "<<l1<<" "<<l2;
	return 0;
}