Cod sursa(job #1218866)

Utilizator crysstyanIacob Paul Cristian crysstyan Data 12 august 2014 19:22:06
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
#include <fstream>
#include <queue>

const int dx[]={1,1,1,-1,-1,-1,0,0};
const int dy[]={-1,0,1,-1,0,1,1,-1};
using namespace std;

char t[105];
int romeo[101][101],julieta[101][101],i,j,n,m,rezx,rezy,bestx=200000000,besty=200000000,best,bestf=200000000;
ifstream f("rj.in");
ofstream g("rj.out");

struct rj{
int x;
int y;};

queue <rj> q,p;

bool inside (int x,int y){
if (x>=1 && x<=n && y>=1 && y<=m)
return 1;
else
return 0;
    }

    rj initial_romeo,initial_julieta;

    void traseu_romeo(){
    q.push(initial_romeo);
    while (!q.empty())
    {
        rj coordr=q.front();
        q.pop();
        for (i=0; i<=7; i++)
        {
            rj newcoordr;
            newcoordr.x=coordr.x+dx[i];
            newcoordr.y=coordr.y+dy[i];

            if (romeo[newcoordr.x][newcoordr.y]==-1 && romeo[newcoordr.x][newcoordr.y]!=-2 && inside (newcoordr.x,newcoordr.y)==1){
           romeo[newcoordr.x][newcoordr.y]=romeo[coordr.x][coordr.y]+1;
           q.push(newcoordr);
            }
        }
    }
    }

    void traseu_julieta(){
    p.push(initial_julieta);
    while (!p.empty())
    {
        rj coordj=p.front();
        p.pop();
        for (i=0; i<=7; i++)
        {
            rj newcoordj;
            newcoordj.x=coordj.x+dx[i];
            newcoordj.y=coordj.y+dy[i];

            if (julieta[newcoordj.x][newcoordj.y]==-1 && inside(newcoordj.x,newcoordj.y==1)){
            julieta[newcoordj.x][newcoordj.y]=julieta[coordj.x][coordj.y]+1;
            p.push(newcoordj);
            }
        }
    }
    }

    int main ()
    {
        f>>n>>m;
        f.get();
        for (i=1; i<=n; i++){
            f.getline(t,110);
        for (j=0; j<=m; j++)



            if (t[j]==' '){
            romeo[i][j]=-1;
            julieta[i][j]=-1;
            }
            else
            if (t[j]=='X'){
            romeo[i][j]=-2;
            julieta[i][j]=-2;}
            else if (t[j]=='R'){
            romeo[i][j]=1;
            initial_romeo.x=i;
            initial_romeo.y=j;
            q.push(initial_romeo);
            }
            else
            if (t[j]=='J'){
            julieta[i][j]=1;
            initial_julieta.x=i;
            initial_julieta.y=j;
            p.push(initial_julieta);
            }

        }

        traseu_romeo();
        traseu_julieta();
     /*   for (i=1; i<=n; i++)
        {
            for (j=0; j<=m-1; j++)
            {
                g<<julieta[i][j]<<" ";
            }
            g<<'\n';
        }
        for (i=1; i<=n; i++)
        {
            for (j=0; j<=m-1; j++)
            {
                g<<romeo[i][j]<<" ";
            }
            g<<'\n';
        }
*/
        for (i=1; i<=n; i++)
        for (j=0; j<=m-1; j++)
        if (romeo[i][j]==julieta[i][j] && romeo[i][j]>0)
        {
            rezx=i; rezy=j+1; best=romeo[i][j];
            if (rezx<bestx) bestx=rezx;
            if (rezy<besty) besty=rezy;
            if (best<bestf) bestf=best;

        }
        g<<bestf<<" "<<bestx<<" "<<besty;
        return 0;
    }