Cod sursa(job #1373455)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 4 martie 2015 18:52:11
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define fin "rj.in"
#define fou "rj.out"
using namespace std;
int romeo[102][102],juliet[102][102];
struct poz{int l,c;} c[10203];
struct poz1{int l,c;} c2[10203];
int main()
{
    int m,n,p1c,p1l,p2c,p2l,i,j,li1,lc1,li2,lc2,prec1[10203],prec2[10203],lcrt,ccrt,u,p,dl[9],dc[9],gasit=0,dist1,dist2,minim,pfl,pfc;
    char x[101];
    ifstream t1(fin);
    ofstream t2(fou);
    t1>>m>>n;
    t1.get();
    for(i=1;i<=m;i++){ t1.get(x,101); cout<<x<<'\n';; t1.get(); for(j=1;j<=n;j++) { if(x[j-1]=='X') { romeo[i][j]=-1; juliet[i][j]=-1; } if(x[j-1]=='R') { romeo[i][j]=1; p1l=i; p1c=j; li1=i; lc1=j; } if(x[j-1]=='J') { juliet[i][j]=1; p2l=i; p2c=j; li2=i; lc2=j;} if(x[j-1]==' ') { romeo[i][j]=0; juliet[i][j]=0;} } }
    for(i=0;i<=m+1;i++) {romeo[i][0]=-1; juliet[i][0]=-1; romeo[i][n+1]=-1; juliet[i][n+1]=-1;}
    for(i=0;i<=n+1;i++) {romeo[0][i]=-1; juliet[0][i]=-1; romeo[m+1][i]=-1; juliet[m+1][i]=-1;}
    u=1; p=1;
    cout<<p1l<<" "<<p1c<<" "<<p2l<<" "<<p2c<<'\n';;
    c[u].l=li1;
    c[u].c=lc1;
    prec1[1]=0;
    dl[1]=-1; dl[2]=-1; dl[3]=-1; dl[4]=0; dl[5]=1; dl[6]=1; dl[7]=1; dl[8]=0;
    dc[1]=-1; dc[2]=0; dc[3]=1; dc[4]=1; dc[5]=1; dc[6]=0; dc[7]=-1; dc[8]=-1;
    while(p<=u && !gasit)
    {
        lcrt=c[p].l; ccrt=c[p].c;
        for(i=1;i<=8;i++)
        {
            if(romeo[lcrt+dl[i]][ccrt+dc[i]]==0)
            {
                romeo[lcrt+dl[i]][ccrt+dc[i]]=1+romeo[lcrt][ccrt];
                u++;
                c[u].l=lcrt+dl[i]; c[u].c=ccrt+dc[i]; prec1[u]=p;
            }
            if(lcrt==p2l && ccrt==p2c) gasit=1;
        }
        p++;
    }
    dist1=romeo[p2l][p2c];
    u=1; p=1;
    c2[u].l=li2;
    c2[u].c=lc2;
    prec2[1]=0;
    gasit=0;
    while(p<=u && !gasit)
    {
        lcrt=c2[p].l; ccrt=c2[p].c;
        for(i=1;i<=8;i++)
        {
            if(juliet[lcrt+dl[i]][ccrt+dc[i]]==0)
            {
                juliet[lcrt+dl[i]][ccrt+dc[i]]=1+juliet[lcrt][ccrt];
                u++;
                c2[u].l=lcrt+dl[i]; c2[u].c=ccrt+dc[i]; prec2[u]=p;
            }
            if(lcrt==p1l && ccrt==p1c) gasit=1;
        }
        p++;
    }
    dist2=juliet[p1l][p1c];
    minim=10202;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            if(juliet[i][j]==romeo[i][j] && romeo[i][j]<minim && romeo[i][j]>0)
            {
                minim=romeo[i][j];
                pfl=i; pfc=j;
            }
    t2<<minim<<" "<<pfl<<" "<<pfc;
    t2<<'\n';
    return 0;
}