Cod sursa(job #2663947)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 27 octombrie 2020 17:28:42
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
//
//  main.cpp
//  rj
//
//  Created by Eusebiu Rares on 27/10/2020.
//  Copyright © 2020 Eusebiu Rares. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <queue>

typedef std::pair<int, int> PII ;

const int NMAX = 100 ;

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

char mat[1 + NMAX][1 + NMAX] ;
int costR[1 + NMAX][1 + NMAX] ;
int costJ[1 + NMAX][1 + NMAX] ;
int n, m ;

bool inbounds(int x, int y) {
	return 1 <= x && x <= n && 1 <= y && y <= m ;
}

FILE *in = fopen("rj.in", "r"), *out = fopen("rj.out", "w") ;

void bfs(PII src, int seen[][1 + NMAX]) {
	std::queue<PII> bfsQueue ;
	bfsQueue.push(src) ;
	while (!bfsQueue.empty()) {
		PII top = bfsQueue.front() ;
		bfsQueue.pop() ;
		for (int i = 1 ; i <= 4 ; ++ i) {
			int xx = top.first + dx[i] ;
			int yy = top.second + dy[i] ;
			if (seen[top.first][top.second] + 1 < seen[xx][yy] && inbounds(xx, yy) && mat[xx][yy] != 'X') {
				seen[xx][yy] = seen[top.first][top.second] + 1 ;
				bfsQueue.push({xx, yy}) ;
			}
		}
	}
}

int main(int argc, const char * argv[]) {
	fscanf(in, "%d %d\n", &n, &m) ;
	PII juliet, romeo ;
	for (int i = 1 ; i <= n ; ++ i) {
		bool skip(false) ;
		for (int j = 1 ; j <= m ; ++ j) {
			mat[i][j] = fgetc(in) ;
			costR[i][j] = costJ[i][j] = 1e8 ;
			if (mat[i][j] == '\n') {
				for ( ; j <= m ; ++ j) {
					mat[i][j] = ' ' ;
				}
				skip = true ;
				break ;
			}
			if (mat[i][j] == 'J') {
				juliet = {i, j} ;
				costJ[i][j] = 0 ;
			} else if (mat[i][j] == 'R') {
				romeo = {i, j} ;
				costR[i][j] = 0 ;
			}
		}
		if (!skip)
			fgetc(in) ;
	}
	bfs(juliet, costJ) ;
	bfs(romeo, costR) ;
	int x(0), y(0), best(1000000) ;
	for (int i = 1 ; i <= n ; ++ i) {
		for (int j = 1 ; j <= m ; ++ j) {
//			fputc(mat[i][j], out) ;
			if (costR[i][j] == costJ[i][j] && costJ[i][j] > 0) {
				if (costR[i][j] < best) {
					best = costR[i][j] ;
//					std::cout << best << ' ' << i << ' ' << j << '\n' ;
					x = i ;
					y = j ;
				}
			}
		}
//		fputc('\n', out) ;
	}
	fprintf(out, "%d %d %d", best, x, y) ;
}