Cod sursa(job #2295333)

Utilizator lonca.sorin01Lonca Sorin lonca.sorin01 Data 3 decembrie 2018 16:16:09
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>

using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

queue<int>cx, cy;

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


int main()
{
    int matR[102][102], matJ[102][102], n, m, i, j, k, istartr, jstartr, ifinalr, jfinalr, iactual, jactual, istartj, jstartj, ifinalj, jfinalj;
    char mat[102][102], x[100];
    f>>n>>m;
    f.get();
    for (i = 1; i <= n; i++)
    {
        f.getline(x, 110);
        for (j = 0; j < m; j++)
        {
            if (x[j] == 'R')
            {
                istartr = i;
                jstartr = j + 1;
            }
            if (x[j] == 'J')
            {
                istartj = i;
                jstartj = j + 1;
            }
            if (x[j] == ' ')
                mat[i][j + 1] = '0';
            else
                mat[i][j + 1] = x[j];
        }
    }

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
            matR[i][j] = 9999;
    }

    matR[istartr][jstartr] = 1;
    cx.push(istartr);
    cy.push(jstartr);
    while (!cx.empty())
    {
        iactual = cx.front();
        jactual = cy.front();
        cx.pop();
        cy.pop();
        for (k = 0; k < 8; k++)
        {
            if (matR[iactual][jactual] + 1 < matR[iactual + dx[k]][jactual + dy[k]] && mat[iactual + dx[k]][jactual + dy[k]] != 'X')
            {
                matR[iactual + dx[k]][jactual + dy[k]] = matR[iactual][jactual] + 1;
                cx.push(iactual + dx[k]);
                cy.push(jactual + dy[k]);
            }
        }
    }

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
            matJ[i][j] = 9999;
    }

    matJ[istartj][jstartj] = 1;
    cx.push(istartj);
    cy.push(jstartj);
    while (!cx.empty())
    {
        iactual = cx.front();
        jactual = cy.front();
        cx.pop();
        cy.pop();
        for (k = 0; k < 8; k++)
            if (matJ[iactual][jactual] + 1 < matJ[iactual + dx[k]][jactual + dy[k]] && mat[iactual + dx[k]][jactual + dy[k]] != 'X')
            {
                matJ[iactual + dx[k]][jactual + dy[k]] = matJ[iactual][jactual] + 1;
                cx.push(iactual + dx[k]);
                cy.push(jactual + dy[k]);
            }
    }
    int mn = 9999, imn, jmn;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            if (matR[i][j] == matJ[i][j] && matR[i][j] < mn)
            {
                mn = matR[i][j];
                imn = i;
                jmn = j;
            }
        }
    g<<mn<<" "<<imn<<" "<<jmn;
    return 0;
}