Cod sursa(job #2221077)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 13 iulie 2018 01:27:57
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <fstream>
#include <queue>
#include <deque>

using namespace std;

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

const int di[8] = {-1, 1, 0, 0, -1, 1, 1, -1};
const int dj[8] = {0, 0, 1, -1, 1, 1, -1, -1};

int mat[105][105];
int n, m, i, j, i2, j2, dir, x1, x2, y1, y2, startx, starty, stopx, stopy, cnt;

char c[105];

queue < pair<int, int> > Q;
deque < pair<int, int> > traseu;

bool isOK (int i, int j)
{
    if (i < 1 || j < 1 || i > n || j > n)
        return false;
    return !mat[i][j];
}

void Lee()
{
    int i, j, i2, j2, dir;
    Q.push({startx, starty});
    mat[startx][starty] = 1;
    while (!Q.empty()){
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for (dir=0; dir<8; dir++){
            i2 = i + di[dir];
            j2 = j + dj[dir];
            if (isOK(i2, j2)){
                mat[i2][j2] = mat[i][j] + 1;
                Q.push({i2, j2});
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    fin.get();
    for (i=1; i<=n; i++){
        fin.getline(c, m + 1);
        for (j=1; j<=m; j++){
            if (c[j-1] == ' ')
                mat[i][j] = 0;
            if (c[j-1] == 'X')
                mat[i][j] = -1;
            if (c[j-1] == 'R'){
                x1 = i;
                y1 = j;
            }
            if (c[j-1] == 'J'){
                x2 = i;
                y2 = j;
            }
        }
    }
    if (x1 < x2){
        startx = x1;
        starty = y1;
        stopx = x2;
        stopy = y2;
    }
    else if (x1 > x2){
        startx = x2;
        starty = y2;
        stopx = x1;
        stopy = y1;
    }
    else{
        startx = x1;
        startx = min(y1, y2);
        stopx = x2;
        stopy = max(y1, y2);
    }
    Lee();
    fout << (mat[stopx][stopy]+1)/2 << " ";
    i = n;
    j = n;
    traseu.push_back({n, n});
    while (i > 1 || j > 1){
        for (dir=0; dir<8; dir++){
            i2 = i + di[dir];
            j2 = j + dj[dir];
            if (mat[i2][j2] == mat[i][j] - 1){
                i = i2;
                j = j2;
                traseu.push_back({i, j});
                break;
            }
        }
        i--;
        j--;
    }
    //while (!traseu.empty()){
        //cnt++;
    fout << traseu.back().first << " " << traseu.back().second << "\n";
        //traseu.pop_back();
    //}
    return 0;
}