Cod sursa(job #2391701)

Utilizator DumitresculEDumitrescul Eduard DumitresculE Data 29 martie 2019 09:37:55
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("rj.in");
ofstream fout("rj.out");
string s;
int x[105][105], a[105][105], b[105][105];
int di[8]={-1, -1, 0, 1, 1, 1, 0, -1}, dj[8]={0, 1, 1, 1, 0, -1, -1, -1};
void lee_a(int i, int j, int k){
    int p;
    for (p=0; p<=7; p++){
        if(x[i+di[p]][j+dj[p]] == 0 and (a[i+di[p]][j+dj[p]]==0 or a[i+di[p]][j+dj[p]]>k))
            a[i+di[p]][j+dj[p]]=k, lee_a(i+di[p], j+dj[p], k+1);
    }
}

void lee_b(int i, int j, int k){
    int p;
    for (p=0; p<=7; p++){
        if(x[i+di[p]][j+dj[p]] == 0 and (b[i+di[p]][j+dj[p]]==0 or b[i+di[p]][j+dj[p]]>k))
            b[i+di[p]][j+dj[p]]=k, lee_b(i+di[p], j+dj[p], k+1);
    }
}

int main()
{
    int n, m, i, j, x1, x2, y1, y2;
    fin >> n >> m;
    getline(fin, s);
    for (i=1; i<=n; i++){
        getline(fin, s);
        for (j=0; j<s.size(); j++)
            if(s[j]=='X')
                x[i][j+1]=-1;
            else if(s[j] == 'R')
                x1 = i, y1 = j+1;
            else if(s[j] == 'J')
                x2 = i, y2 = j+1;
    }
    for (i=0; i<=n+1; i++){
        x[i][0] = x[i][m+1] = -1;
        a[i][0] = a[i][m+1] = -1;
        b[i][0] = b[i][m+1] = -1;
    }

    for (j=0; j<=m+1; j++){
        x[0][j] = x[n+1][j] = -1;
        a[0][j] = a[n+1][j] = -1;
        b[0][j] = b[n+1][j] = -1;
    }

    a[x1][y1] = b[x2][y2] = 1;
    lee_a (x1, y1, 2);
    lee_b (x2, y2, 2);

    int pasi = 1 + (a[x2][y2] - 1)/2;
    fout << 1 + (a[x2][y2] - 1)/2 << " ";

    int minn=9999999,p1,p2;
    for (i=1; i<=n; i++){
        for (j=1; j<=m; j++)
            if(x[i][j]==0 and a[i][j]!=0 and b[i][j]!=0)
            if(pasi == a[i][j] and (pasi == b[i][j] or pasi==b[i][j]-1))
                p1=i, p2=j;
    }

    fout << p1 << " " << p2 << "\n";
    return 0;
}