Cod sursa(job #1836359)

Utilizator alexandra_paticaAndreea Alexandra Patica alexandra_patica Data 28 decembrie 2016 12:14:18
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
using namespace std;
ifstream cin ("rj.in");
ofstream cout ("rj.out");

struct punct
{
    short l, c;
}r[10001], J[10001];

int n, m, i, j, xr, yr, xj, yj, nr[102][102], nj[102][102], p, u, la, ca, cv, lv;
bool a[102][102];
char c[101];
short dx[]={-1, -1, 0, 1, 1, 1, 0, -1}, dy[]={0, 1, 1, 1, 0, -1, -1, -1};

int main ()
{
    cin >> n >> m;
    cin.get();
    for (i=1; i<=n; i++){
        cin.getline(c, 101);
//        cout << c << '\n';
        for (j=0; j<m; j++){
            if (c[j]=='X') a[i][j+1]=1;
            else if (c[j]==' ') a[i][j+1]=0;
            else if (c[j]=='R'){
                xr=i; yr=j+1;
            }
            else if (c[j]=='J'){
                xj=i; yj=j+1;
            }
            nr[i][j+1]=10000000;
            nj[i][j+1]=10000000;
        }
    }
//    for (i=1; i<=n; i++){
//        for (j=1; j<=m; j++) cout << a[i][j] << " ";
//        cout << '\n';
//    }

    for (i=0; i<=n+1; i++)
        a[i][0]=a[i][m+1]=1;
    for (j=0; j<=m+1; j++)
        a[0][j]=a[n+1][j]=1;

    p=u=1;
    r[1].l=xr; r[1].c=yr;
    J[1].l=xj; J[1].c=yj;
    nr[xr][yr]=1;
    nj[xj][yj]=1;
    while (p<=u){
        la=r[p].l;
        ca=r[p].c;
        for (i=0; i<8; i++){
            lv=la+dx[i];
            cv=ca+dy[i];
            if (a[lv][cv]==0 && nr[lv][cv]>nr[la][ca]+1){
                u++;
                r[u].l=lv; r[u].c=cv;
                nr[lv][cv]=nr[la][ca]+1;
            }
        }
        p++;
    }
    p=u=1;
    while (p<=u){
        la=J[p].l;
        ca=J[p].c;
        for (i=0; i<8; i++){
            lv=la+dx[i];
            cv=ca+dy[i];
            if (a[lv][cv]==0 && nj[lv][cv]>nj[la][ca]+1){
                u++;
                J[u].l=lv; J[u].c=cv;
                nj[lv][cv]=nj[la][ca]+1;
            }
        }
        p++;
    }
//    cout << '\n';
//     for (i=1; i<=n; i++){
//        for (j=1; j<=m; j++) cout << nr[i][j] << " ";
//        cout << '\n';
//    }
//    cout << '\n';
//     for (i=1; i<=n; i++){
//        for (j=1; j<=m; j++) cout << nj[i][j] << " ";
//        cout << '\n';
//    }

    ca=10000000;
    for (i=1; i<=n; i++){
        for (j=1; j<=m; j++){
            if (nr[i][j]==nj[i][j]){
                if (nr[i][j]<ca){
                    ca=nr[i][j];
                    la=i; lv=j;
                }
            }
        }
    }
    cout << ca << " " << la << " " << lv;
    return 0;
}