Cod sursa(job #2307167)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 23 decembrie 2018 20:39:13
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>
#define DIM 105
#define	inf 2000000000
#define x first
#define y second
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,m,i,j,timp,rom[DIM][DIM],jul[DIM][DIM],xmin,ymin,x1,y1,x2,y2;
char a[DIM][DIM],s[DIM];
int di[10]={-1, 1, 0, 0, -1, 1, 1, -1};
int dj[10]={0, 0, 1, -1, 1, 1, -1, -1};
queue< pair<int,int> > q;
bool valid(int i,int j) {
    if (i<1||j<1||i>n||j>m)
        return false;
    if (a[i][j]=='X')
        return false;
    return true;
}
void lee(int xstart,int ystart,int drum[DIM][DIM]) {
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			drum[i][j]=0;
	drum[xstart][ystart]=1;
	q.push({xstart,ystart});
	while (!q.empty()) {
		i=q.front().x;
		j=q.front().y;
		q.pop();
		for (int dir=0;dir<8;dir++) {
			int iv=i+di[dir];
			int jv=j+dj[dir];
			if (valid(iv,jv)&&drum[iv][jv]==0) {
				drum[iv][jv]=drum[i][j]+1;
				q.push({iv,jv});
			}
		}
	}
}
int main() {
	fin>>n>>m;
	fin.get();
	for (i=1;i<=n;i++){
        fin.getline(s,m+1);
        for (j=1;j<=m;j++){
            a[i][j]=s[j-1];
            if (s[j-1]=='R')
                x1=i, y1=j;
            if (s[j-1]=='J')
                x2=i, y2=j;
        }
    }
	timp=DIM*DIM;
	lee(x1,y1,rom);
	lee(x2,y2,jul);
	for (i=1;i<=n;i++) {
		for (j=1;j<=m;j++) {
			if (rom[i][j]==jul[i][j]) {
				if (rom[i][j]<timp&&rom[i][j]!=0) {
					timp=rom[i][j];
					xmin=i; ymin=j;
				}
			}
		}
	}
	fout<<timp<<" "<<xmin<<" "<<ymin;
	return 0;
}