Cod sursa(job #1260848)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 11 noiembrie 2014 17:49:25
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <fstream>
#include <cstring>
#define Inf 0x3f3f3f3f
#define Mat 105
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
const int dx[9] = {0, 1, 0,-1, 0, 1,-1, 1,-1};
const int dy[9] = {0, 0, 1, 0,-1,-1, 1, 1,-1};
struct lee
{
    unsigned char lin,col;
}c[Mat*Mat],p,v;
int n,m,a[Mat][Mat],b[Mat][Mat],i,j,x1,x2,y1,y2,prim,ultim,mn,jmn,imn;
char x[Mat];
int main()
{
    f >> n >> m;
    f.get();
    for(i = 1; i <= n; i++){
        f.getline(x,Mat);
        for(j = 0; j < m; j++){
            if(x[j]==' ') {a[i][j+1] = 0; b[i][j+1] = 0;}
            if(x[j]=='X') {a[i][j+1] = -1; b[i][j+1] = -1;}
            if(x[j]=='J') {a[i][j+1] = 1; x1=i;y1=j+1;}
            if(x[j]=='R') {b[i][j+1] = 1; x2=i;y2=j+1;}
        }
    }
    mn = Inf;
    jmn = Inf;
    imn = Inf;
    //bordare
    for(i = 0; i <= n+1; i ++){
        a[i][0] = -1; b[i][0] = -1;
        a[i][m+1] = -1; b[i][m+1] = -1;

    }
    for(i = 0;i <= m+1; i++){
        a[0][i] = -1; b[0][i] = -1;
        a[n+1][i] = -1; b[n+1][i] = -1;
    }
    //Lee pe julieta
    prim = 0;
    ultim = 0;
    p.lin = x1; p.col = y1;
    c[0] = p;
    while(prim <= ultim){
        p = c[prim ++];
        for(i = 1; i <= 8; i++){
            v.lin= p.lin + dx[i];
            v.col= p.col + dy[i];
            if(a[v.lin][v.col] == 0){
                a[v.lin][v.col] = a[p.lin][p.col] + 1;
                c[++ultim] = v;
            }
        }
    }
    //Lee pe robeo
    prim = 0;
    ultim = 0;
    p.lin = x2; p.col = y2;
    c[0] = p;
    while(prim <= ultim){
        p = c[prim ++];
        for(i = 1; i <= 8; i++){
            v.lin= p.lin + dx[i];
            v.col= p.col + dy[i];
            if(b[v.lin][v.col] == 0){
                b[v.lin][v.col] = b[p.lin][p.col] + 1;
                if(b[v.lin][v.col] == a[v.lin][v.col]){
                    if(b[v.lin][v.col] <= mn){
                        mn = b[v.lin][v.col];
                        if(v.lin <= imn){
                            if(v.lin==imn && v.col < jmn){
                                    jmn = v.col;
                                    imn = v.lin;
                                }
                            else
                            {
                            jmn = v.col;
                            imn = v.lin;
                            }

                        }
                    }
                }
                c[++ultim] = v;
            }
        }
    }
    g << mn <<" "<<imn<<" "<<jmn;
    return 0;
}