Cod sursa(job #1369708)

Utilizator devilz05Orzan Alexandru devilz05 Data 3 martie 2015 10:46:59
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.24 kb
#include <iostream>
#include <queue>
#include <stdio.h>
using namespace std;

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

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

char **read(int *n, int *m)
{
    FILE *f = fopen("rj.in", "r");
    char **map = NULL;
    int i, j;
    
    fscanf(f, "%i%i", 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 ((map[i][j] = fgetc(f)) == '\n');
    
    fclose(f);
    return map;
}

void _findPath(char **map, int &n, int &m, Point start, Point &end, int &step, Point *pathTemp, queue<Point*> &path)
{
    if (start.x < 0 || start.x > n-1 || start.y < 0 || start.y > m - 1)
        return;
    
    char c = map[start.x][start.y];
    if (c == ' ' || c == 'R' || c == 'J')
    {
        map[start.x][start.y] = 'X';
        pathTemp[step++].set(start.x, start.y, step > 0 ? pathTemp[step-1].i + start.x : start.x, step > 0 ? pathTemp[step-1].j + start.y : start.y);
        
        if (start.x == end.x && start.y == end.y && (path.size() > step || path.empty() || (path.size() == step && path.back()->i > pathTemp[step-1].i) ||
            (path.size() == step && path.back()->i == pathTemp[step-1].i && path.back()->j > pathTemp[step-1].j)))
        {
            while (!path.empty())
            {
                delete path.front();
                path.pop();
            }
            for (int i=0; i<step; ++i)
                path.push(new Point(pathTemp[i].x, pathTemp[i].y, pathTemp[i].i, pathTemp[i].j));
                
        }
        else
            for (int i = 0; i < 8; ++i)
                _findPath(map, n, m, Point(start.x + dx[i], start.y + dy[i]), end, step, pathTemp, path);
        
        map[start.x][start.y] = c;
        --step;
    }
}

void findPath(char **map, int n, int m)
{
    queue<Point*> pathF;
    Point *pathTemp = new Point[n*m], *best = NULL;;
    Point romeo(-1, -1), juliet(-1, -1);
    int i, j, tmin, x, y;
    bool even = false;
    
    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);
        }
    
    i = 0;
    _findPath(map, n, m, romeo, juliet, i, pathTemp, pathF);
    
    if ((pathF.size() & 1) == 0) even = true;
    tmin = (pathF.size() / 2) + (even ? 0 : 1);
    j = (pathF.size() / 2) + (even ? -1 : 0);
    
    for (i = 0; i < j; ++i)
        pathF.pop();
    best = pathF.front();
    pathF.pop();
    
    if (even && (best->x > pathF.front()->x || (best->x == pathF.front()->x && best->y > pathF.front()->y)))
        best = pathF.front();
    
    FILE *f = fopen("rj.out", "w");
    fprintf(f, "%i %i %i", tmin, best->x+1, best->y+1);
    fclose(f);
}

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