Cod sursa(job #2657893)

Utilizator stanbianca611Stan Bianca stanbianca611 Data 12 octombrie 2020 17:01:33
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

ifstream f ("rj.in");
ofstream g ("rj.out");

int n, m, a[105][105], b[105][105];

pair<int, int> r, j;
deque<pair<int, int>> q;
priority_queue<tuple<int, int, int>> pq;
int dl[]={-1, 0, 1, 0, -1, 1, -1, 1};
int dc[]={0, 1, 0, -1, -1, 1, 1, -1};

bool check(int x, int y)
{
    if(x>=1 && y>=1 && x<=n && y<=m && a[x][y]==0)
        return 1;
    return 0;
}

int main()
{
    f>>n>>m;
    char x;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<m; j++)
        {
            f.get(x);
            b[i][j+1]=1000;
            if(x=='R')
                {
                    q.push_back(make_pair(i, j+1));
                    a[i][j+1]=0;
                    b[i][j+1]=0;
                }
            else if(x=='J')
                {
                    q.push_back(make_pair(i, j+1));
                    a[i][j+1]=0;
                    b[i][j+1]=0;
                }
            else if(x=='X')
            {
                a[i][j+1]=-1;
            }
            else
            {
                a[i][j+1]=0;
            }
        }
    }
    pair<int, int> curr, next;
    while(!q.empty())
    {
        curr=q.front();
        q.pop_front();
        //ma uit in toate cele 8 directii
        for(int i=0; i<8; i++)
        {
            next.first=curr.first+dl[i];
            next.second=curr.second+dc[i];
            if(check(next.first, next.second))
            {
                if(b[curr.first][curr.second]+1<b[next.first][next.second])//daca am gasit un drum mai scurt
                {
                     b[next.first][next.second]=b[curr.first][curr.second]+1;
                     q.push_back(make_pair(next.first, next.second));
                }
                else if (b[curr.first][curr.second]+1==b[next.first][next.second])
                {
                    pq.push(make_tuple(-b[next.first][next.second], next.first, next.second));
                }
            }
        }
    }
    g<<-get<0>(pq.top())+1<<" "<<get<1>(pq.top())<<" "<<get<2>(pq.top());
    return 0;
}