Cod sursa(job #1896691)

Utilizator robert_fanrRobert Banu robert_fanr Data 28 februarie 2017 20:39:08
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.52 kb
// 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;
}