Cod sursa(job #3184935)

Utilizator AlexanderCernyCernaianu Alexandru AlexanderCerny Data 17 decembrie 2023 13:49:57
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <iostream>
#include <fstream>
#define DIM 101
#include <queue>
#include <climits>

using namespace std;

ifstream fin ("rj.in");
ofstream fout("rj.out");

int n,m,i,j,ir,jr,ij,jj;
char ch[DIM];
int tmin=INT_MAX,is,js;
bool a[DIM][DIM];
int dr[DIM][DIM];
int dj[DIM][DIM];
int dx[]={0, -1, -1, -1, 0, 1, 1, 1, 0};
int dy[]={0, -1, 0, 1, 1, 1, 0, -1, -1};
struct coada
{
    int lin;
    int col;
};
queue<coada>Q;
void bfs(int x, int y, int d1[DIM][DIM], int d2[DIM][DIM])
{
    Q.push({x,y});
    d1[x][y]=1;
    while(!Q.empty())
    {
        int l=Q.front().lin,c=Q.front().col;
        for(int i=1;i<=8;i++)
        {
            int lv=l+dx[i],cv=c+dy[i];
            if(lv>=1&&lv<=n&&cv>=1&&cv<=m)
                if(a[lv][cv]==0 && d1[lv][cv]==0)
                {
                    Q.push({lv,cv});
                    d1[lv][cv]=d1[l][c]+1;
                    if(d2[lv][cv]==d1[lv][cv])
                    {
                        if(d2[lv][cv]<tmin)
                        {
                            tmin=d2[lv][cv];
                            is=lv;
                            js=cv;
                        }
                    }
                }
        }
        Q.pop();
    }
}
int main()
{
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;i++)
    {
        fin.getline(ch,DIM);
        for(j=1;j<=m;j++)
        {
            if(ch[j-1]!=' ')
            {
                if(ch[j-1]=='X')
                    a[i][j]=1;
                if(ch[j-1]=='R')
                {
                    ir=i;
                    jr=j;
                }
                if(ch[j-1]=='J')
                {
                    ij=i;
                    jj=j;
                }
            }
        }
    }
    bfs(ir, jr, dr, dj);
    bfs(ij, jj, dj, dr);
    fout<<tmin<<" "<<is<<" "<<js;
    return 0;
}