Cod sursa(job #3265768)

Utilizator Mate0Mateo Chiras Mate0 Data 3 ianuarie 2025 11:14:51
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <bits/stdc++.h>
using namespace std;

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

int main()
{
    int n, m, ir, ij, jr, jj;
    f >> n >> m;
    int mat[n + 2][m + 2];
    char x;
    string line;
    getline(f, line);
    for(int i = 1; i <= n; i++){
        getline(f, line);
        for(int j = 1; j <= m; j++){
            x = line[j - 1];
            while(x == '\n') f.get(x);
            if(x == 'X') mat[i][j] = -1;
            else if(x == 'R'){
                mat[i][j] = -1;
                ir = i, jr = j;
            }
            else if(x == 'J'){
                mat[i][j] = -1;
                ij = i, jj = j;
            }
            else mat[i][j] = 0;
        }
    }
    for(int i = 0; i <= n + 1; i++){
        mat[i][0] = mat[i][m + 1] = -1;
    }
    for(int i = 0; i <= m + 1; i++){
        mat[0][i] = mat[n + 1][i] = -1;
    }

    struct poz{
        int lin, col;
    } st[5000];

    int d = 0, nre = 1;
    st[1].lin = ir;
    st[1].col = jr;

    int vi[8] = {0, 0, 1, -1, 1, -1, -1, 1}, vj[8] = {1, -1, 0, 0, 1, -1, 1, -1};

    while(d < nre){
        d++;
        for(int i = 0; i < 8; i++){
            if(mat[st[d].lin + vi[i]][st[d].col + vj[i]] == 0){
                st[nre + 1].lin = st[d].lin + vi[i];
                st[nre + 1].col = st[d].col + vj[i];
                if(mat[st[d].lin][st[d].col] != -1) mat[st[d].lin + vi[i]][st[d].col + vj[i]] = mat[st[d].lin][st[d].col] + 1;
                else mat[st[d].lin + vi[i]][st[d].col + vj[i]] = 1;
                nre++;
            }
        }
    }

    d = 0;
    nre = 1;
    st[1].lin = ij;
    st[1].col = jj;
    int tmin = 10001, ii, ji = 101;

    while(d < nre){
        d++;/*
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cout << mat[i][j] << " ";
            }
            cout << '\n';
        }
        cout << "------" << endl;*/
        for(int i = 0; i < 8; i++){
            if(mat[st[d].lin + vi[i]][st[d].col + vj[i]] > 0){
                if(mat[st[d].lin + vi[i]][st[d].col + vj[i]] > tmin) break;
                if(mat[st[d].lin + vi[i]][st[d].col + vj[i]] == -mat[st[d].lin][st[d].col] && (st[d].col + vj[i] < ji)){
                   tmin = mat[st[d].lin + vi[i]][st[d].col + vj[i]];
                   ii = st[d].lin + vi[i];
                   ji = st[d].col + vj[i];
                }
                //cout << mat[st[d].lin + vi[i]][st[d].col + vj[i]] << " " << -mat[st[d].lin][st[d].col] - 1 << endl;
                st[nre + 1].lin = st[d].lin + vi[i];
                st[nre + 1].col = st[d].col + vj[i];
                mat[st[d].lin + vi[i]][st[d].col + vj[i]] = mat[st[d].lin][st[d].col] - 1;
                nre++;
            }
        }
    }

    g << tmin + 1 << " " << ii << " " << ji;

    return 0;
}