Cod sursa(job #3207115)

Utilizator Hotea_MihaelMihael Hotea Hotea_Mihael Data 25 februarie 2024 11:44:10
Problema Ridicare la putere in timp logaritmic Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <fstream>
#include <queue>
#include <cmath>
using namespace std;
ifstream cin("rj.in");
ofstream cout("rj.out");
queue<pair<int,int>>Q;
const int dx[]= {-1,-1,-1,0,0,1,1,1};
const int dy[]= {0, -1, 1,1,-1,0,-1,1};
int n,m,x1,y11,x2,y2,p[105][105],p1[105][105],mini=99999,lin,col;
char a[105][105];
char c;
bool inmat(int i,int j)
{
    return i>=1 && i<=n && j>=1 && j<=m;
}
void Lee(int i,int j)
{
    Q.push(make_pair(i,j));
    pair<int,int>f;
    while(!Q.empty())
    {
        f=Q.front();
        for(int d=0;d<=7;d++)
        {
            int inou=Q.front().first+dx[d];
            int jnou=Q.front().second+dy[d];
            if(inmat(inou,jnou) && a[inou][jnou]!='X' && p[inou][jnou]==0)
            {
                p[inou][jnou]=p[f.first][f.second]+1;
                Q.push(make_pair(inou,jnou));
            }
        }
        Q.pop();
    }
}
void Lee1(int i,int j)
{
    Q.push(make_pair(i,j));
    pair<int,int>f;
    while(!Q.empty())
    {
        f=Q.front();
        for(int d=0;d<=7;d++)
        {
            int inou=Q.front().first+dx[d];
            int jnou=Q.front().second+dy[d];
            if(inmat(inou,jnou) && a[inou][jnou]!='X' && p1[inou][jnou]==0)
            {
                p1[inou][jnou]=p1[f.first][f.second]+1;
                Q.push(make_pair(inou,jnou));
            }
        }
        Q.pop();
    }
}
int main()
{
    cin>>n>>m;
    cin.get(c);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
        cin.get(c);
        a[i][j]=c;
        if(c=='R')
            x1=i,y11=j;
        if(c=='J')
            x2=i,y2=j;
        }
        cin.get(c);
    }
    p[x1][y11]=1;
    p1[x2][y2]=1;
Lee(x1,y11);
Lee1(x2,y2);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        if( p[i][j]&& p[i][j]==p1[i][j] && p[i][j]<mini)
        lin=i,col=j,mini=p[i][j];
        cout<<lin<<' '<<col<<' '<<mini;
    return 0;
}