Cod sursa(job #2183202)

Utilizator DimaTCDima Trubca DimaTC Data 22 martie 2018 22:01:38
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<bits/stdc++.h>
#define NMAX 105
#define x first
#define y second
using namespace std;

int dx[]={0,-1,-1,-1,0,1,1,1};
int dy[]={-1,-1,0,1,1,1,0,-1};

const int inf=1e9;
int M[2][NMAX][NMAX];
queue<pair<int,int> >Q;
int rs,rsi,rsj,n,m,sri,srj,sji,sjj,rs1,rs2;
int a[NMAX][NMAX];
string s;

bool OK(int i, int j) {
	return (i>=1 && j>=1 && j<=m && i<=n && a[i][j]==0);
}

void Lee(int i, int j, int c) {
	M[c][i][j]=1;
	Q.push({i,j});
	while (Q.size()) {
		i=Q.front().x; j=Q.front().y; Q.pop();
		
		for (int d=0; d<8; d++) {
			int i2=i+dx[d];
			int j2=j+dy[d];
			if (OK(i2,j2) && M[c][i2][j2]>M[c][i][j]+1) {
				M[c][i2][j2]=M[c][i][j]+1;
				Q.push({i2,j2});
			}
		}
	}
}

int main() {
	ifstream cin("rj.in");
	ofstream cout("rj.out");
	
	cin>>n>>m; getline(cin,s);
	for (int i=1; i<=n; i++) {
		getline(cin,s);
		for (int j=0; j<s.size(); j++) {
			if (s[j]=='R') {
				sri=i; srj=j+1;
			} else if (s[j]=='J') {
				sji=i; sjj=j+1;
			} else if (s[j]=='X') a[i][j+1]=1;
		}
	}
	
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) M[0][i][j]=M[1][i][j]=inf;
	}
	
	
	Lee(sri, srj, 0);
	Lee(sji,sjj,1);

	rs=inf;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			if (M[0][i][j]==M[1][i][j] && M[0][i][j]<rs) {
				rs=M[0][i][j];
				rsi=i;
				rsj=j;
			}
		}
	}
	cout<<rs<<" "<<rsi<<" "<<rsj;
	
	return 0;
}