Cod sursa(job #2666132)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 31 octombrie 2020 23:02:20
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.11 kb
/*#include<bits/stdc++.h>
using namespace std;


void dei(int st,int dr,const vector<int>& v,unordered_map<int,vector<int> >& fr,vector<int> & mars)
{
    if(st<dr)
    {
        //cout<<st<<' '<<dr<<'\n';
        int pos = st;
        int baleiere = 0;
        while(pos < dr)
        {
            int culoare = v[pos];
            bool interval = true;
            if(fr[culoare].front() < st || fr[culoare].back() >= dr){
                interval = false;  //nu avem solutie(se suprapun intervalele
                return;
            }
            if(interval && fr[culoare].front() == pos)
            {
                ++baleiere;
                for(int i = 0;i < static_cast<int>(fr[culoare].size()); ++i)
                    if(i+1 < static_cast<int>(fr[culoare].size()))
                        dei(fr[culoare][i]+1,fr[culoare][i+1],v,fr,mars);
                pos = fr[culoare].back() + 1;
            }
        }
        mars[st] += baleiere;
        mars[dr] -= baleiere;
    }
    return;
}

int main()
{
    int n,m;
    cin>>n>>m;
    vector<int> v(n,0);
    for(int i=0;i<n;++i)
        cin>>v[i];
    //retin pt fiecare culoare intervalul
    //imi trebuie capatul stang si drep -> map de frecventa
    unordered_map<int,vector<int> > fr;
    for(int i = 0;i < n;++i)
        fr[v[i]].emplace_back(i);
    int ans = 0;
    for(int i = 1;i <= m;++i)
        if( fr[i].empty() )
            ++ans;
    //cout<<ans;
    vector<int> mars(n+1,0);
    dei(0,n,v,fr,mars);
    int max_depth = 0,ps = 0;
    for(int i:mars)
    {
        ps += i;
        if(max_depth < ps)
            max_depth = ps;
    }
    ans += max_depth;
    cout<<ans;
}*/

/*#include <bits/stdc++.h>
#define nmax 5002
using namespace std;
int main()
{
    int v[nmax];
    int n,sum;
    cin>>n;
    for(int i = 2;i <= n;++i)
    {
        cout<<"?"<<" "<<1<<" "<<i<<'\n'<<std::flush;
        cin>>v[i];
    }
    cout<<"?"<<" "<<2<<" "<<3<<"\n"<<std::flush;
    cin>>sum;
    v[1]=(v[2]+v[3]-sum)/2;

    for(int i = 2;i <= n;++i)
        v[i] -= v[1];

    cout<<"!";
    for(int i = 1;i < n;++i)
        cout<<" "<<v[i];
    cout<<" "<<v[n]<<std::flush;
}*/

#include<bits/stdc++.h>
#define N 102
#define Dim 1e9
#define mp make_pair
#define pii pair<int,int>
using namespace std;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};
int n,m,ri,rj,ji,jj,a[N][N],b[N][N];

bool valid(int x,int y)
{
    return (x>=0 && y>=0 && x<n && y<m);
}

void bfs(int x,int y,int m[N][N])
{
    queue<pii> q;
    q.push(mp(x,y));
    while(!q.empty())
    {
        pii curr=q.front();
        q.pop();
        for(int i=0;i<8;++i)
        {
            int _x=curr.first+dx[i];
            int _y=curr.second+dy[i];
            if(valid(_x,_y) && m[_x][_y]!=-1)
                if(m[_x][_y]>m[curr.first][curr.second]+1)
                {
                    m[_x][_y]=m[curr.first][curr.second]+1;
                    q.push(mp(_x,_y));
                }
        }
    }

}

int main()
{
    ifstream fin("rj.in");
    ofstream fout("rj.out");
    //ofstream fout("rj.out");
    fin>>n>>m;
    fin.get();
    char s[m];
    for(int i=0;i<n;++i){
        string S, T;
        getline(fin, S);
        stringstream X(S);
        while (getline(X, T, '\n')) {
            for(int j=0;j<m;++j)
                {
                    if(T[j]=='R'){
                        a[i][j]=0;b[i][j]=Dim;ri=i;rj=j;continue;}
                    if(T[j]=='J'){
                        a[i][j]=Dim;b[i][j]=0;ji=i;jj=j;continue;}
                    if(T[j]=='X'){
                        a[i][j]=b[i][j]=-1; continue;}
                    else
                        { //poate fi endline fmm
                        //cout<<i<<' '<<j<<endl;
                        a[i][j]=Dim;
                        b[i][j]=Dim;
                        continue;}
                }
        }
        /*fin.getline(s,m);
        cout<<s<<endl;
        for(int j=0;j<m;++j)
        {
            if(s[j]=='R'){
                a[i][j]=0;b[i][j]=Dim;ri=i;rj=j;continue;}
            if(s[j]=='J'){
                a[i][j]=Dim;b[i][j]=0;ji=i;jj=j;continue;}
            if(s[j]=='X'){
                a[i][j]=b[i][j]=-1; continue;}
            else
               { //poate fi endline fmm
                //cout<<i<<' '<<j<<endl;
                a[i][j]=Dim;
                b[i][j]=Dim;
                continue;}
        }*/
    }
    //cout<<ji<<' '<<jj<<endl;
    bfs(ri,rj,a);
    bfs(ji,jj,b);
    /*for(int i=0;i<n;++i){
        for(int j=0;j<m;++j)
            cout<<b[i][j]<<' ';
        cout<<endl;
    }*/
    int time=Dim,sola,solb;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            if(a[i][j]==b[i][j] && a[i][j]!=-1)
            {
                if(time>a[i][j])
                {
                    sola=i;
                    solb=j;
                    time=a[i][j];
                }
            }
    fout<<++time<<' '<<++sola<<' '<<++solb<<'\n';
    fin.close();
    fout.close();

}