Cod sursa(job #2824246)

Utilizator divadddDavid Curca divaddd Data 31 decembrie 2021 18:22:08
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define MAX 102
using namespace std;
int n,m,ir,jr,ij,jj,l[MAX][MAX],c[MAX][MAX];
char v[MAX][MAX];
vector<pair<int,int>> traseuR;
vector<pair<int,int>> traseuJ;

ifstream fin("rj.in");
ofstream fout("test.out");

/// (ir, jr) = pozitie romeo
/// (ij, jj) = pozitie julieta

bool inautru(int i, int j){
    if((1 <= i && i <= n) && (1 <= j && j <= n)){
        return true;
    }
    return false;
}

vector<pair<int,int>> lee(int istart, int jstart, int istop, int jstop){
    queue<pair<int, int>> coada;

    int dl[8] = {-1, -1, -1,  0, 0,  1, 1, 1};
    int dc[8] = {-1,  0,  1, -1, 1, -1, 0, 1};

    l[istart][jstart] = 0;
    coada.push(make_pair(istart, jstart));
    while(!coada.empty()){
        int lin = coada.front().first;
        int col = coada.front().second;

        for(int k = 0; k < 8; k++){
            int linv = lin+dl[k];
            int colv = col+dc[k];

            if(inautru(linv, colv) && l[linv][colv] == 0){
                l[linv][colv] = l[lin][col]+1;
                coada.push(make_pair(linv, colv));
            }
        }
        coada.pop();
    }

    vector<pair<int,int>> traseu;
    int i = istop , j = jstop;
    traseu.push_back(make_pair(i , j));
    do
    {
        int p = -1;
        for(int k = 0 ; k < 8 && p == -1 ; k ++)
            if(l[i][j] == l[i+dl[k]][j+dc[k]] + 1)
                p = k;
        i = i + dl[p] , j = j + dc[p];
        traseu.push_back(make_pair(i , j));
    }
    while(l[i][j] != 1);
    traseu.push_back(make_pair(istart , jstart));
    int tmin = traseu.size()/2+(traseu.size()%2);
    fout << tmin << " ";
    fout << traseu.at(tmin-1).first << " " <<  traseu.at(tmin-1).second << "\n\n";
}

int main()
{
    fin >> n >> m;
    fin.ignore();
    for(int i = 1; i <= n; i++){
        string s;
        getline(fin, s);
        for(int j = 0; j < s.length(); j++){
            if(s[j] == 'X'){
                l[i][j+1] = -1;
            }
            if(s[j] == 'R'){
                ir = i; jr = j+1;
            }
            if(s[j] == 'J'){
                ij = i; jj = j+1;
            }
            c[i][j+1] = l[i][j+1];
        }
    }
    /// traseul lui romeo
    traseuR = lee(ir, jr, ij, jj);
    return 0;
}