Cod sursa(job #2433298)

Utilizator rd211Dinucu David rd211 Data 26 iunie 2019 18:23:15
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int harta[105][105];
int dist[105][105];
char viz[105][105];
char addx[]= {1,0,0,-1,1,-1,1,-1};
char addy[]= {0,1,-1,0,1,-1,-1,1};
int n,m;
bool ok(int x,int y,int vizBy)
{
    if(x<1||y<1||x>n||y>m)
        return false;
    if(vizBy==viz[x][y])
        return false;
    if(harta[x][y]!=0)
        return false;
    return true;
}
queue<pair<int,int>> cue;
void lee()
{
    int closest = 99999999;
    pair<int,int> closestp;

    while(cue.size())
    {
        int x = cue.front().first;
        int y = cue.front().second;
        for(int i = 0; i<8; i++)
        {
            int x2 = x+addx[i];
            int y2 = y+addy[i];
            if(ok(x2,y2,viz[x][y]))
            {
                if(viz[x2][y2]!=0)
                {
                    if(dist[x2][y2]==dist[x][y]+1){
                        if(closest>dist[x2][y2]){
                            closest=dist[x2][y2],closestp.first=x2,closestp.second=y2;
                        }
                        else if(closest==dist[x2][y2]&&closestp.first>x2){
                            closestp.first=x2,closestp.second=y2;
                        }
                    }
                }
                else
                {
                    viz[x2][y2]=viz[x][y];
                    dist[x2][y2]=dist[x][y]+1;
                    cue.push({x2,y2});
                }
            }
        }
        cue.pop();
    }
    fout<<closest<<" "<<closestp.first<<" "<<closestp.second<<'\n';
}
int main()
{
    string s;
    int rx,ry,jx,jy;
    fin>>n>>m;
    getline(fin,s);
    for(int i = 1; i<=n; i++)
    {
        getline(fin,s);
        for(int j = 0; j<s.size(); j++)
        {
            if(s[j]!=' ')
            {
                if(s[j]=='R')
                    harta[i][j+1]=1,rx=i,ry=j+1;
                else if(s[j]=='J')
                    harta[i][j+1]=2,jx=i,jy=j+1;
                else
                    harta[i][j+1]=-1;
            }
        }
    }
    dist[rx][ry]=1;
    dist[jx][jy]=1;
    viz[rx][ry]=1;
    viz[jx][jy]=2;
    cue.push({rx,ry});
    cue.push({jx,jy});
    lee();
    return 0;
}