Cod sursa(job #2615915)

Utilizator MerlinTheWizardMelvin Abibula MerlinTheWizard Data 15 mai 2020 19:54:49
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <queue>
#include <fstream>
#include<iostream>
#include<string.h>
using namespace std;
ifstream f ("rj.in");
ofstream g ("rj.out");

struct coord
{
    int x, y;
};
int u;
char a[105][105];
int b[105][105];
int c[105][105];
int n, m;
char p;
int xs, ys, xf, yf;
int x1,x2;
int min1=99999999;
int minx,miny;
void Citire()
{
    int i, j;
    f >> n >> m;
    f.get();
    for (i = 1; i <=n; i++)
    {
            f.getline(a[i]+1,101);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='R')
            {
                xs=i;
                ys=j;
            }
            if(a[i][j]=='J')
            {
                xf=i;
                yf=j;
            }
        }
}

void Bordare()
{
    int i, j;
    for (j = 0; j < n + 1; j++)
    {
        a[0][j] = a[n + 1][j] = 'X';    // obstacol
    }
    for (i = 0; i < m + 1; i++)
    {
        a[i][0] = a[i][m + 1] = 'X';    // obstacol
    }
}

void Lee()
{
    int i, j;
    queue <coord> q;
    coord w, w1;
    int dx[] = { 0, 1, 0, -1, 1, -1, 1, -1};
    int dy[] = { 1, 0, -1, 0, 1, -1, -1, 1};
    w.x = xs;
    w.y = ys;
    q.push(w);
     a[xs][ys] = 'X';
    while (!q.empty())
    {
        w = q.front();
        q.pop();

        for (i = 0; i < 8; i++)
        {
            w1.x = w.x + dx[i];
            w1.y = w.y + dy[i];
            if (a[w1.x][w1.y] == ' ' && (b[w1.x][w1.y] == 0) || (b[w.x][w.y] + 1 < b[w1.x][w1.y]))
            {
                b[w1.x][w1.y] = b[w.x][w.y] + 1;
                q.push(w1);
            }
        }
    }
}

void Lee1()
{
    int i, j;
    queue <coord> q;
    coord w, w1;
    int dx[] = { 0, 1, 0, -1, 1, -1, 1, -1};
    int dy[] = { 1, 0, -1, 0, 1, -1, -1, 1};
    w.x = xf;
    w.y = yf;
    q.push(w);
     a[xf][yf] = 'X';
    while (!q.empty())
    {
        w = q.front();
        q.pop();

        for (i = 0; i < 8; i++)
        {
            w1.x = w.x + dx[i];
            w1.y = w.y + dy[i];
            if (a[w1.x][w1.y] == ' ' && (c[w1.x][w1.y] == 0) || (c[w.x][w.y] + 1 < c[w1.x][w1.y]))
            {
                c[w1.x][w1.y] = c[w.x][w.y] + 1;
                q.push(w1);
            }
        }
    }
}

void Afisare()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(b[i][j]!=0 && c[i][j]==b[i][j] && min1>b[i][j])
            {
                min1=b[i][j];
                minx=i;
                miny=j;
            }
        }
    }

    g<<min1+1<<" "<<minx<<" "<<miny;
}
int main()
{
    Citire();
    Bordare();
    Lee();
    Lee1();
    Afisare();
}