Pagini recente » Cod sursa (job #2696187) | Cod sursa (job #1573410) | Cod sursa (job #435606) | Cod sursa (job #2359075) | Cod sursa (job #2663947)
//
// 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) ;
}