Cod sursa(job #2478536)

Utilizator AlexPopescuPopescu Alexandru AlexPopescu Data 22 octombrie 2019 12:43:52
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
#define dmax 104

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

int r[dmax][dmax], n, m, tmin=1e9;
int ju[dmax][dmax], k;
int dx[]={-1, -1, 0, 1, 1,  1,  0, -1};
int dy[]={ 0,  1, 1, 1, 0, -1, -1, -1};
char str[dmax];
void bordare(){
	int i;
	for (i=0;i<=n+1;i++){
		r[i][0]=r[i][m+1]=-1;
		ju[i][0]=ju[i][m+1]=-1;
	}
	for (i=0;i<=m+1;i++){
		r[0][i]=r[n+1][i]=-1;
		ju[0][i]=ju[n+1][i]=-1;
	}
}

struct P{
	int x, y;
}p, vec, start1, start2, fin;

queue <P> coada;

void citire(){
	int i, j;
	cin>>n>>m;
	cin.get();
	for (i=1;i<=n;i++){
		cin.getline(str, dmax);
		for (j=0;j<m;j++){
			if (str[j]=='X')
				r[i][j+1]=ju[i][j+1]=-1;
			else if (str[j]==' ')
				r[i][j+1]=ju[i][j+1]=-0;
			else if (str[j]=='R'){
				start1.x=i;
				start1.y=j+1;
			}
            else if (str[j]=='J'){
				start2.x=i;
				start2.y=j+1;
			}
		}
	}
	bordare();
}

bool ok(int i, int j){
	return 1<=i&&i<=n&&1<=j&&j<=m&&r[i][j]==0;
}
bool ok1(int i, int j){
	return 1<=i&&i<=n&&1<=j&&j<=m&&ju[i][j]==0;
}
void LeeR(){
    r[start1.x][start1.y]=1;
	coada.push(start1);
	while (!coada.empty()){
		p=coada.front();
		coada.pop();
		for (k=0;k<8;k++){
			vec.x=p.x+dx[k];
			vec.y=p.y+dy[k];
			if (ok(vec.x, vec.y)){
				r[vec.x][vec.y]=r[p.x][p.y]+1;
				coada.push(vec);
			}
		}
	}
}

void LeeJ(){
	coada.push(start2);
    ju[start2.x][start2.y]=1;
	while (!coada.empty()){
		p=coada.front();
		coada.pop();
		for (k=0;k<8;k++){
			vec.x=p.x+dx[k];
			vec.y=p.y+dy[k];
			if (ok1(vec.x, vec.y)){
				ju[vec.x][vec.y]=ju[p.x][p.y]+1;
				coada.push(vec);
			}
		}
	}
}

int main()
{
	citire();
	LeeR();
	LeeJ();
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (r[i][j]==ju[i][j]&&r[i][j]>0&&tmin>r[i][j]){
				tmin=r[i][j];
				fin.x=i;
				fin.y=j;
			}
	cout<<tmin<<" "<<fin.x<<" "<<fin.y;
	cin.close();
	cout.close();
	return 0;
}