Cod sursa(job #1629874)

Utilizator KanghuAndre Popescu Kanghu Data 4 martie 2016 19:35:30
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#include <string>

using namespace std;

int mat[101][101];
int m, n;
int minim = 10000;

int di[] = { -1, 0, 1, 0 };
int dj[] = { 0, 1, 0, -1 };

ifstream i("rj.in");
ofstream o("rj.out");

struct pos
{
    int x, y;
};

int drum(int x, int y)
{
    if(mat[x][y] == minim + 1)
    {
        o << x << " " << y;
        return 0;
    }

    int j,k, t;
    t = 10000;

    pos l;

    for(int a = 0; a < 4; a++)
    {
        j = x + di[a];
        k = y + dj[a];

        if( (mat[j][k] < t) && (mat[j][k] > 0) )
        {
            t = mat[j][k];
            l.x = j;
            l.y = k;
        }
    }

    return drum(l.x, l.y);
}

int main()
{

    string k;
    pos start;
    pos finish;

    i >> m >> n;

    getline(i, k);

    for(int a = 1; a <= m; a++)
    {
        getline(i, k);

        char j[100];
        strcpy(j, k.c_str());

        for(int b = 1; b <= n; b++)
        {
            if(j[b - 1] == 'X')
            {
                mat[a][b] = -1;
            }

            else if(j[b - 1] == ' ')
            {
                mat[a][b] = 0;
            }

            else if(j[b - 1] == 'R')
            {
                start.x = a;
                start.y = b;

                mat[a][b] = 1;
            }

            else if(j[b - 1] == 'J')
            {
                mat[a][b] = -2;
            }
        }
    }

    for(int a = 0; a <= n; a++)
    {
        mat[a][0] = -1;
        mat[a][m + 1] = -1;
    }

    for(int a = 0; a <= m; a++)
    {
        mat[0][a] = -1;
        mat[n + 1][a] = -1;
    }

    queue<pos> coada;
    coada.push(start);

    while(!coada.empty())
    {
        pos curr = coada.back();
        coada.pop();

        for(int a = 0; a < 4; a++)
        {
            int x = curr.x + di[a];
            int y = curr.y + dj[a];

            if(mat[x][y] == 0)
            {
                mat[x][y] = mat[curr.x][curr.y] + 1;

                pos t;
                t.x = x;
                t.y = y;

                coada.push(t);
            }

            if(mat[x][y] == -2)
            {
                if(mat[curr.x][curr.y] < minim)
                {
                    minim = mat[curr.x][curr.y];
                }

                finish.x = x;
                finish.y = y;
            }
        }
    }

   drum(finish.x, finish.y);

   if(minim)
   {
       minim = minim / 2;
       o << minim << " ";
   }

   else
   {
       minim = minim / 2 + 1;
       o << minim << " ";
   }

    return 0;
}