Pagini recente » Cod sursa (job #1265005) | Cod sursa (job #723949) | Cod sursa (job #1845278) | Cod sursa (job #969372) | Cod sursa (job #1896691)
// Rj infoarena.cpp : Defines the entry point for the console application.
//
//#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <list>
#include <limits>
#include <cstdio>
using namespace std;
ifstream in("rj.in.txt"); //a se inlatura txt la final
ofstream out("rj.out");
const int N_MAX = 102;
char c;
int n, m;
int distR[N_MAX][N_MAX], distJ[N_MAX][N_MAX]; //in astea vom calcula distanta de la rom/jul la fiecare punct liber
struct punct {
int i, j;
} rom, jul;
void citire() {
FILE * in_h = fopen("rj.in","r");
//FILE ** pointer = &in_h;
//fopen(pointer, "rj.in.txt", "r");
char trash;
fscanf_s(in_h,"%d %d", &n, &m);
int i, j;
for (i = 1; i <= n; i++) {
trash = 0;
while (trash != '\n') {
fscanf(in_h, "%c", &trash);
}
for (j = 1; j <= m; j++) {
fscanf(in_h, "%c", &c);
if (c == 'R') {
rom.i = i; rom.j = j; //aici se afla Romeo
}
if (c == 'J') {
jul.i = i; jul.j = j; //aici se afla Julieta
}
if (c == ' ')
distR[i][j] = distJ[i][j] = 2000000000;//INT_MAX;
}
}
}
int iDirectie[9] = { 0, -1, -1, -1, 0, 1, 1, 1, 0 };
int jDirectie[9] = { 0, -1, 0, 1, 1, 1, 0, -1, -1 };
//calculeaza dist pt Rom
void BFS_R() {
list <punct> queue;
queue.push_back(rom);
while (!queue.empty()) {
punct curent = queue.front();
queue.pop_front();
int k;
for (k = 1; k <= 9; k++) {
//se updateaza distanta curenta daca e cazul si in caz afirmativ acesta e trecut in coada
if (distR[curent.i + iDirectie[k]][curent.j] + jDirectie[k])
if (distR[curent.i + iDirectie[k]][curent.j + jDirectie[k]] > distR[curent.i][curent.j] + 1) {
distR[curent.i + iDirectie[k]][curent.j + jDirectie[k]] = distR[curent.i][curent.j] + 1;
punct nou; nou.i = curent.i + iDirectie[k]; nou.j = curent.j + jDirectie[k];
queue.push_back(nou);
}
}
}
}
//calculeaza dist pt Jul
void BFS_J() {
list <punct> queue;
queue.push_back(jul);
while (!queue.empty()) {
punct curent = queue.front();
queue.pop_front();
int k;
for (k = 1; k <= 9; k++) {
//se updateaza distanta curenta daca e cazul si in caz afirmativ acesta e trecut in coada
if (distR[curent.i + iDirectie[k]][curent.j] + jDirectie[k])
if (distJ[curent.i + iDirectie[k]][curent.j + jDirectie[k]] > distJ[curent.i][curent.j] + 1) {
distJ[curent.i + iDirectie[k]][curent.j + jDirectie[k]] = distJ[curent.i][curent.j] + 1;
punct nou; nou.i = curent.i + iDirectie[k]; nou.j = curent.j + jDirectie[k];
queue.push_back(nou);
}
}
}
}
//cauta punctul de intalnire
void pctIntalnire() {
int tmin = 2000000000/*INT_MAX*/, x=0, y=0;
int i, j;
for (i=1; i<=n; i++)
for (j = 1; j <= m; j++) {
if (distR[i][j])
if (distR[i][j] == distJ[i][j])
if (distR[i][j] < tmin) {
tmin = distR[i][j];
x = i;
y = j;
}
}
out << tmin+1 << " " << x << " " << y;
}
int main()
{
citire();
BFS_R();
BFS_J();
pctIntalnire();
return 0;
}