Cod sursa(job #1153793)

Utilizator veruxyTeste G veruxy Data 25 martie 2014 18:54:45
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include<fstream>
#include<cstring>
#include<iostream>
 
using namespace std;
 
int di[]={-1,0,1,0,1,1,-1,-1}; //initializare pentru avansare
int dj[]={0,1,0,-1,1,-1,1,-1};
 
int n,i,j,a1[155][155],q[10001][2],nq,pq,k,ni,nj,m;
int a2[155][155],x1,x2,y1,y2;
char c[155][155],s[101],s1[5],*p;
 
ifstream f("rj.in");
ofstream g("rj.out");
 
int ok(int i,int j,int n,int m)
{
    if(i>0&&i<=n&&j>0&&j<=m) return 1; //verificam daca am iesit din matrice
    return 0;
}
 
void citire()
{
    f.getline(s,101);
    p=strtok(s," ");
    for(i=0;i<strlen(p);i++)
       n=n*10+(p[i]-'0');
    p=strtok(NULL," ");
    for(i=0;i<strlen(p);i++)
        m=m*10+(p[i]-'0');
    for(i=1;i<=n;i++)
    {f.getline(s,101);
    for(j=0;j<m;j++)
    {
        if(s[j]=='R')
        {
            x1=i; y1=j+1;
            a1[i][j+1]=0;
            c[i][j+1]='R';
        }
        else if(s[j]=='J')
        {
            x2=i; y2=j+1;
            a2[i][j+1]=0;
            c[i][j+1]='J';
        }
        else if(s[j]=='X')
            c[i][j+1]='X';
        else c[i][j+1]='*';
    }}
}
 
void rezolva(int a[][155],int x,int y)
{
    pq=0;
    nq=1;
    q[pq][0]=x;
    q[pq][1]=y;
    while(pq<nq)
    {
        i=q[pq][0]; //pozitia liniei
        j=q[pq][1];
        for(k=0;k<8;k++)
        {
            ni=i+di[k]; //avansarea in matrice
            nj=j+dj[k];
            if(ok(ni,nj,n,m)&&(c[ni][nj]=='*')&& (a[ni][nj]==-1))
            {
                a[ni][nj]=a[i][j]+1;
                q[nq][0]=ni;
                q[nq][1]=nj;
                nq++;
            }
        }
    pq++;}
 
}
 
 
int main()
{int minim=10001,lin=200,col=200;
    //memset(a1,-1,sizeof(a1));
    //memset(a2,-1,sizeof(a2));
      
    citire();
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            a1[i][j]=a2[i][j]=-1;
    a1[x1][y1]=a2[x2][y2] =0;      
//    cout<<x1<<" "<<y1<<endl;
    rezolva(a1,x1,y1);
    rezolva(a2,x2,y2);
 /*  for(i=1;i<=n;i++){
        for(j=1;j<=m;j++)
            cout<<c[i][j];
        cout<<endl;    
} 

cout<<x2<<" "<<y2<<endl; 
 for(i=1;i<=n;i++){
        for(j=1;j<=m;j++)
            cout<<a2[i][j]<<" ";
        cout<<endl;    
}       */
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        if(a1[i][j]==a2[i][j] && a1[i][j]>=0 && a1[i][j]<minim)
                {minim=a1[i][j]; lin=i; col=j;}
  
    g<<minim+1<<" "<<lin<<" "<<col;
}