Cod sursa(job #1586585)

Utilizator Firealex2Rotileanu Alexandru Firealex2 Data 1 februarie 2016 13:54:31
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <iostream>
#include <fstream>
#include <string>


using namespace std;

ifstream fi("rj.in");
ofstream fo("rj.out");

struct coada{
    int x,y;
};
coada c[200000];
int mat[101][101],matj[101][101];
int start=1,ultim=2;
coada romeo,julieta;
int r=0;

int dl[]={-1,0,1,0};
int dc[]={0,1,0,-1};

int main()
{
    int n,m,i,j;
    fi>>n>>m;
    fi.ignore();
    string a;
    for(i=1;i<=n;i++)
    {
        getline(fi,a);
        for(j=0;j<m;j++)
        {
            if(a[j]==' ')
                {
                    mat[i][j+1]=0;
                    matj[i][j+1]=0;
                }
            else if(a[j]=='X')
                    {
                        mat[i][j+1]=-1;
                        matj[i][j+1]=-1;
                    }
                else
                {
                    if(a[j]=='R')
                        romeo={i,j+1};
                    if(a[j]=='J')
                        julieta={i,j+1};
                    mat[i][j+1]=1;
                    matj[i][j+1]=1;

                }
        }
    }
    for(i=0;i<=n+1;i++)
        {
            mat[i][0]=-1;
            mat[i][m+1]=-1;
            matj[0][i]=-1;
            matj[n+1][i]=-1;
        }
    for(i=0;i<=m+1;i++)
        {
            mat[0][i]=-1;
            mat[n+1][i]=-1;
            matj[0][i]=-1;
            matj[n+1][i]=-1;
        }
    c[start]=romeo;
    int min=0;
    while(start<ultim)
    {
        for(i=0;i<4;i++)
        {
            if(mat[c[start].x+dl[i]][c[start].y+dc[i]]==0)
            {
                c[ultim].x=c[start].x+dl[i];
                c[ultim].y=c[start].y+dc[i];
                mat[c[start].x+dl[i]][c[start].y+dc[i]]=mat[c[start].x][c[start].y]+1;
                ultim++;
            }
        }
        start++;
    }
    //for(i=1;i<=n;i++)
    //{
     //   for(j=1;j<=m;j++)
     //   {
    //        cout<<mat[i][j]<<" ";
     //   }
   //     cout<<endl;
  //  }
    c[++start]=julieta;
    ultim+=2;
    while(min==0)
    {
        for(i=0;i<4;i++)
        {
            if(matj[c[start].x+dl[i]][c[start].y+dc[i]]==0)
            {
                c[ultim].x=c[start].x+dl[i];
                c[ultim].y=c[start].y+dc[i];
                if(mat[c[start].x+dl[i]][c[start].y+dc[i]]==matj[c[start].x][c[start].y]+1)
                    {
                        min=matj[c[start].x][c[start].y]+1;
                        julieta.x=c[start].x+dl[i];
                        julieta.y=c[start].y+dc[i];
                        break;
                    }
                else matj[c[start].x+dl[i]][c[start].y+dc[i]]=matj[c[start].x][c[start].y]+1;
                ultim++;
            }
        }
        start++;
    }
    fo<<min-1<<" "<<julieta.x<<" "<<julieta.y;


    return 0;
}