Cod sursa(job #2399074)

Utilizator andu2006Alexandru Gheorghies andu2006 Data 6 aprilie 2019 20:28:59
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include<bits/stdc++.h>
#define NMAX 104
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int m1[NMAX][NMAX],m2[NMAX][NMAX],n,m;
pair<int,int> start,finish;
int dc[8]={-1,0,1,0,1,1,-1,-1};
int dl[8]={0,1,0,-1,1,-1,1,-1};
void cpy()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            m2[i][j]=m1[i][j];
            m1[i][j]=min(m1[i][j],0);
        }
    }
}
void lee()
{
    pair<int,int> aux;
    queue<pair<int,int>> q;
    q.push(start);
    while(q.size())
    {
        for(int i=0;i<8;i++)
        {
            aux.first=q.front().first+dc[i];
            aux.second=q.front().second+dl[i];
            if(m1[aux.first][aux.second]==0 && aux.first>0 && aux.first<=n && aux.second>0 && aux.second<=m)
            {
                m1[aux.first][aux.second]=m1[q.front().first][q.front().second]+1;
                q.push(aux);
            }
        }
        q.pop();
    }
}
int main()
{
    char aux[NMAX];
    fin>>n>>m;
    memset(m1,0,sizeof(m1));
    memset(m2,0,sizeof(m2));
    fin.getline(aux,1);
    for(int i=1;i<=n;i++)
    {
        fin.getline(aux,NMAX-1);
        for(int j=1;j<=m;j++)
        {
            if(aux[j-1]=='R')
            {
                start.first=i;
                start.second=j;
            }
            else if(aux[j-1]=='J')
            {
                finish.first=i;
                finish.second=j;
            }
            else if(aux[j-1]=='X')
                m1[i][j]=-1;
            aux[j-1]='\0';
        }
    }
    //cout<<start.first<<" "<<start.second<<'\n';
    m1[start.first][start.second]=1;
    lee();
    start=finish;
    //cout<<finish.first<<" "<<finish.second;
    cpy();
    m1[start.first][start.second]=1;
    lee();
    int mini=1000000,p1=0,p2=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(m1[i][j]>0 && m1[i][j]==m2[i][j] && m1[i][j]<mini)
            {
                mini=m1[i][j];
                p1=i;
                p2=j;
            }
        }
    }
    fout<<mini<<" "<<p1<<" "<<p2;
    return 0;
}