Cod sursa(job #1140506)

Utilizator alexsuciuAlex Suciu alexsuciu Data 12 martie 2014 02:22:03
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 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[120][120],q1[4500][2],nq,pq,k,ni,nj,m;
int a2[120][120],q2[4500][2];
char c[101][101],s[110];

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>>n>>m;
    f.getline(s,110);
    for(i=1;i<=n;i++)
    {f.getline(s,101);
    for(j=0;j<m;j++)
    {
        if(s[j]=='R')
        {
            q1[0][0]=i;
            q1[0][1]=j+1;
            a1[i][j+1]=0;
            c[i][j+1]=' ';
        }
        else if(s[j]=='J')
        {
            q2[0][0]=i;
            q2[0][1]=j+1;
            a2[i][j+1]=0;
            c[i][j+1]=' ';
        }
        else if(s[j]=='X')
            c[i][j+1]='X';
        else c[i][j+1]=' ';
    }}
}

void rezolva(int a[120][120],int q[4500][2])
{
    pq=0;
    nq=1;
    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))
            {
                a[ni][nj]=a[i][j]+1;
                q[nq][0]=ni;
                q[nq][1]=nj;
                nq++;
            }
        }
    pq++;}

}


int main()
{int minim=10000,lin=200,col=200;
    memset(a1,-1,sizeof(a1));
    memset(a2,-1,sizeof(a2));
    citire();
    rezolva(a1,q1);
    rezolva(a2,q2);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        if(a1[i][j]==a2[i][j] && a1[i][j]!=-1 && a1[i][j]!=0 && a1[i][j]<=minim)
    {
        if(a1[i][j]==minim && i<lin) {lin=i; col=j;}
        else if(a1[i][j]==minim && i==lin && j<col) {lin=i; col=j;}
        else if(minim>a1[i][j])
            {minim=a1[i][j]; lin=i; col=j;}
    }
    g<<minim+1<<" "<<lin<<" "<<col;
}