Cod sursa(job #2490834)

Utilizator banduraul0Bandu Raul banduraul0 Data 11 noiembrie 2019 01:33:30
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.35 kb
#include<iostream>
#include<cstring>
#include<fstream>
#include<climits>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
struct coordonata
{
    int x, y;
} C[41000], k, vecin, plecare;
int tmin = INT_MAX, N, M, x, y, romeo[101][101], julieta[101][101], dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
char a[101][101];
void Lee(coordonata plecare, int mat[101][101])
{
    int i, prim = 0, ultim = 0;
    C[0] = plecare;
    while(prim <= ultim)
    {
        k = C[prim];
        for(i = 0; i <= 7; i++)
        {
            vecin.x = k.x + dx[i];
            vecin.y = k.y + dy[i];
            if(a[vecin.x][vecin.y] == ' ')
            {
                if(mat[vecin.x][vecin.y] == 0)
                {
                    mat[vecin.x][vecin.y] = mat[k.x][k.y] + 1;
                    C[++ultim]=vecin;
                }
                else if(mat[vecin.x][vecin.y] > mat[k.x][k.y] + 1)
                {
                    mat[vecin.x][vecin.y] = mat[k.x][k.y] + 1;
                    C[++ultim]=vecin;
                }
            }
        }
        prim++;
    }
}
int main()
{
    int i, j;
    in>>N>>M;
    in.ignore();
    //bordarea matricei
    for(i = 0; i <= N + 1; i++)
        a[i][0] = '#';
    for(i = 1; i <= N; i++)
    {
        char s[101];
        in.getline(s, M + 1);
        strcat(a[i], s);
    }
    for(i = 0; i <= N + 1; i++)
        a[i][M + 1] = '#';
    for(i = 0; i <= M + 1; i++)
        a[0][i] = a[N+1][i] = '#';
    for(i = 1; i <= N; i++)
        for(j = 1; j <= M; j++)
        {
            if(a[i][j] == 'R')
            {
                romeo[i][j] = 1;
                plecare.x = i;
                plecare.y = j;
                Lee(plecare, romeo);
            }
            else if(a[i][j] == 'J')
            {
                julieta[i][j] = 1;
                plecare.x = i;
                plecare.y = j;
                Lee(plecare, julieta);
            }
        }
    for(i = 1; i <= N; i++)
        for(j = 1; j <= M; j++)
        {
            if(romeo[i][j] == julieta[i][j])
                if(romeo[i][j] != 0 && romeo[i][j] < tmin)
                {
                    tmin = romeo[i][j];
                    x = i;
                    y = j;
                }
        }
    out<<tmin<<" "<<x<<" "<<y;
}