Cod sursa(job #3185244)

Utilizator manutrutaEmanuel Truta manutruta Data 18 decembrie 2023 16:46:27
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <string>
#define MAX_MAT 100
using namespace std;
ifstream f ("rj.in");
ofstream g ("rj.out");

vector<string> rj;
short dist[MAX_MAT][MAX_MAT];
short dist2[MAX_MAT][MAX_MAT];

int N, M, x1, y1, x2, y2;
int x,y,CX,CY;
queue <int> qx,qy;
const int dx[] = {-1, -1, -1,  0, 0,  1, 1, 1};
const int dy[] = {-1,  0,  1, -1, 1, -1, 0, 1};
bool le2 = false;

bool onmap(int x, int y)
{
    return (0 <= x && x < N &&
            0 <= y && y < M);
}

void lee(int p1, int p2, short dist[][MAX_MAT]){

    qx.push(p1);
    qy.push(p2);
    dist[p1][p2] = 1;

    while(!qx.empty())
    {

        x=qx.front();
        y=qy.front();

        qx.pop();
        qy.pop();

        for(int i=0;i<8;i++)
        {
            CX = x + dx[i];
            CY = y + dy[i];

            if (!onmap(CX, CY)) continue;
            if (rj[CX][CY] == 'X') continue;

            if(dist[CX][CY] == 0)
            {
                qx.push(CX);
                qy.push(CY);
                dist[CX][CY] = dist[x][y] + 1;
            }
        }
    }
}
char punct;

int main()
{
    f>>N>>M;
    rj.resize(N);

    string trash;
    getline(f, trash);

    for(int i=0;i<N;i++)
    {
        getline(f, rj[i]);
    }

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (rj[i][j] == 'R')
            {
                x1 = i;
                y1 = j;
            }
            if (rj[i][j] == 'J')
            {
                x2 = i;
                y2 = j;
            }
        }
    }
    lee(x1, y1, dist);
    /*for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (dist[i][j] <= 9) cout << ' ';
            cout << dist[i][j] << ' ';
        }
        cout << '\n';
    }*/
    lee(x2, y2, dist2);
    /*cout << endl << endl;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (dist[i][j] <= 9) cout << ' ';
            cout << dist2[i][j] << ' ';
        }
        cout << '\n';
    }*/
    int costmin = 100010;
    int xmin = MAX_MAT + 1;
    int ymin = MAX_MAT + 1;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (dist[i][j] != 0 && dist[i][j] == dist2[i][j] && costmin > dist[i][j])
            {
                costmin = dist[i][j];
                xmin = i;
                ymin = j;
            }
        }
    }

    g << costmin << ' ' << xmin+1 << ' ' << ymin+1 << endl;

    return 0;
}