Cod sursa(job #2588331)

Utilizator As932Stanciu Andreea As932 Data 24 martie 2020 17:31:36
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");

const int nmax=105;
const int mmax=105;

int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

int n,m,a[nmax][mmax],mn[nmax][mmax];
struct cell
{
    int x,y;
};
deque <cell> d;

void read_data()
{
    char c,b[mmax];

    fin>>n>>m;
    fin.get(c);

    for(int i=1;i<=n;i++)
    {
        fin.getline(b,m+2);
        for(int j=0;j<m;j++)
            if(b[j]=='R' || b[j]=='J')
                a[i][j+1]=-2,d.push_back({i,j+1});
            else if(b[j]=='X')
                a[i][j+1]=-1;
    }
}

bool okei(int lin,int col)
{
    if(lin>=1 && lin<=n && col>=1 && col<=m)
        return true;
    return false;
}

void bfs_alg()
{
    bool ok=false;
    while(!d.empty() && !ok)
    {
        int lin=d.front().x;
        int col=d.front().y;
        d.pop_front();

        for(int k=0;k<8 && !ok;k++)
        {
            int l1=lin+dx[k];
            int c1=col+dy[k];

            if(okei(l1,c1) && a[l1][c1]==0)
            {
                if(mn[l1][c1]==0)
                {
                    mn[l1][c1]=mn[lin][col]+1;
                    d.push_back({l1,c1});
                }
                else if(mn[lin][col]+1==mn[l1][c1])
                {
                    fout<<mn[l1][c1]+1<<" ";
                    fout<<l1<<" "<<c1;
                    ok=true;
                }
            }
        }
    }
}

void display()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            fout<<mn[i][j]<<" ";
        fout<<"\n";
    }
}

int main()
{
    read_data();
    bfs_alg();
    //display();


    return 0;
}