Cod sursa(job #1369839)

Utilizator devilz05Orzan Alexandru devilz05 Data 3 martie 2015 11:43:10
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.05 kb
#include <iostream>
#include <queue>
#include <fstream>
#include <string>

#define DIRECTIONS 8

using namespace std;

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

struct Point
{
    short int x, y;
    Point(short int x = 0, short int y = 0) : x(x), y(y) {};
    void set(short int x = 0, short int y = 0) {this->x = x; this->y = y;}
};

char **read(short int *n, short int *m)
{
    ifstream f("rj.in");
    char **map = NULL;
    short int i, j;
    
    f >> *n >> *m;
    
    map = new char*[*n];
    for (i = 0; i<*n; ++i)
        map[i] = new char[*m];
    
    for (i=0; i<*n; ++i)
        for (j=0; j<*m; ++j)
            while (f.get(map[i][j]) && map[i][j] == '\n');
    
    f.close();
    return map;
}

bool check(char **map, short int n, short int m, short int x, short int y)
{
    if (x < 0 || x > n-1 || y < 0 || y > m-1 || map[x][y] == 'X')
        return false;
    return true;
}

void Lee(char **map, short int n, short int m, short int **path, short int x0, short int y0)
{
    queue<Point *> Q;
    
    for (short int i = 0; i < n; ++i)
        for (short int j = 0; j < m; ++j)
            path[i][j] = -1;
    
    Q.push(new Point(x0, y0));
    path[x0][y0] = 1;
    while (!Q.empty())
    {
        Point *p = Q.front();
        Q.pop();
        
        for (short int i = 0; i < DIRECTIONS; ++i)
        {
            short int x = p->x + dx[i], y = p->y + dy[i];
            
            if (check(map, n, m, x, y) && path[x][y] == -1)
            {
                path[x][y] = path[p->x][p->y] + 1;
                Q.push(new Point(x, y));
            }
        }
        delete p;
    }
}

void findPath(char **map, short int n, short int m)
{
    Point romeo, juliet;
    short int **pathR = NULL, **pathJ = NULL;
    short int i, j, tmin, x, y;
    
    pathR = new short int*[n];
    pathJ = new short int*[n];
    for (i = 0; i < n; ++i)
    {
        pathR[i] = new short int[m];
        pathJ[i] = new short int[m];
    }
    
    for (i = 0; i < n; ++i)
        for (j = 0; j < m; ++j)
        {
            if (map[i][j] == 'R')
                romeo.set(i, j);
            else if (map[i][j] == 'J')
                juliet.set(i, j);
        }
    
    Lee(map, n, m, pathR, romeo.x, romeo.y);
    Lee(map, n, m, pathJ, juliet.x, juliet.y);
    
    tmin = n*m;
    x = y = -1;
    for (i = 0; i < n; ++i)
    {
        for (j = 0; j < m; ++j)
        {
            if (pathR[i][j] == pathJ[i][j])
            {
                if (pathR[i][j] < tmin && pathR[i][j] != -1)
                {
                    tmin = pathR[i][j];
                    x = i;
                    y = j;
                }
            }
        }
    }
    
    ofstream f("rj.out");
    f << tmin << " " << x+1 << " " << y+1;
    f.close();
}

int main()
{
    char **map = NULL;
    short int n = 0, m = 0;
    
    map = read(&n, &m);
    findPath(map, n, m);
    
    return 0;
}