Cod sursa(job #1521103)

Utilizator CraiuAndrei Craiu Craiu Data 9 noiembrie 2015 22:03:41
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int n, m, rx, ry, jx, jy, xf ,yf, cmin;
int a[105][105], r[105][105], ju[105][105];
char c[200];
int dx[]={-1, -1, 0, 1, 1,  1,  0, -1};
int dy[]={ 0,  1, 1, 1, 0, -1, -1, -1};

struct Coord
{
    int x, y;
};

queue <Coord> q;

bool ok(int i, int j)
{
    if(i > 0 && i <= n && j > 0 && j <= m)  return true;
    return false;
}

void Lee1(int xs, int ys)
{
    int i, j, x, y, k;
    Coord w, w1;
    w.x = xs;
    w.y = ys;
    q.push(w);
    r[xs][ys] = 1;
    while(!q.empty())
    {
        w = q.front();
        x = w.x;
        y = w.y;
        q.pop();
        for(k = 0; k < 8; k++)
        {
            i = x + dx[k];
            j = y + dy[k];
            if(ok(i, j) && (r[i][j] > r[x][y] + 1 || r[i][j] == 0) && (a[i][j] == 0))
            {
                r[i][j] = r[x][y] + 1;
                w1.x = i;
                w1.y = j;
                q.push(w1);
            }
        }
    }
}

void Lee2(int xs, int ys)
{
    int i, j, x, y, k;
    Coord w, w1;
    w.x = xs;
    w.y = ys;
    q.push(w);
    ju[xs][ys] = 1;
    while(!q.empty())
    {
        w = q.front();
        x = w.x;
        y = w.y;
        q.pop();
        for(k = 0; k < 8; k++)
        {
            i = x + dx[k];
            j = y + dy[k];
            if(ok(i, j) && (ju[i][j] > ju[x][y] + 1 || ju[i][j] == 0) && (a[i][j] == 0))
            {
                ju[i][j] = ju[x][y] + 1;
                w1.x = i;
                w1.y = j;
                q.push(w1);
            }
        }
    }
}

int main()
{
    int i, j;

    ifstream fin("rj.in");
    ofstream fout("rj.out");

    fin >> n >> m;
    fin.getline(c, 200);
    for(i = 1; i <= n ; i++)
    {
        fin.getline(c, 200);
        for(j = 0; j <= m; j++)
            if(c[j] == 'X') a[i][j + 1] = 1;
            else if(c[j] == 'R')
            {
                rx = i;
                ry = j + 1;
            }
            else if(c[j] == 'J')
            {
                jx = i;
                jy = j + 1;
            }
    }
    Lee1(rx, ry);
    Lee2(jx, jy);
    cmin = 1000000000;
    /*for(i = 1; i<= n;i++)
    {
        for(j = 1;j<=m;j++)
            fout<<r[i][j]<<" ";
        fout<<endl;
    }
    fout<<endl;
    for(i = 1; i<= n;i++)
    {
        for(j = 1;j<=m;j++)
            fout<<ju[i][j]<<" ";
        fout<<endl;
    }*/
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            if(r[i][j] != 0 && ju[i][j] != 0 && r[i][j] == ju[i][j] && r[i][j] < cmin)
            {
                cmin = r[i][j];
                xf = i;
                yf = j;
            }
    fout << cmin << " " << xf << " " << yf;
    return 0;
}