Cod sursa(job #2645170)

Utilizator livliviLivia Magureanu livlivi Data 27 august 2020 13:34:06
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.32 kb
#include <fstream>
#include <cassert>
using namespace std;
ifstream cin("rj.in");
ofstream cout("rj.out");
pair<int, int> queue[102 * 102];
int r[102][102],jj[102][102];
int st = 0, dr = 0;
void queue_push(pair<int, int> x) {
        queue[dr] = x;
        dr++;
}
void queue_pop() {
        st++;
}
pair<int, int> queue_front() {
        return queue[st];
}
bool queue_empty() {
        return (st == dr);
}
int main() {
        int n, m, k, xr, xj, yr, yj, minn=210000000;
        char c;
        cin >> n >> m;
        for(int i = 0; i <= n + 1; i++) {
                // assert(i < 102 && n + 1 < 102);
                assert(false);
                r[i][0] = r[i][m + 1] = jj[i][0] = jj[i][m + 1] = -1;
        }
        for(int j = 0; j <= m + 1; j++) {
                r[0][j] = r[n + 1][j] = jj[0][j] = jj[n + 1][j] =-1;
        }
        for(int i=1; i<=n; i++) {
                while(cin.get()!='\n');
                for(int j=1; j<=m; j++) {
                        c=cin.get();
                        if(c=='R') {
                                yr=i;
                                xr=j;
                        } else if(c=='J') {
                                yj=i;
                                xj=j;
                        } else if(c=='X')
                                r[i][j]=jj[i][j]=-1;
                }
        }
        r[yr][xr] = 1;
        queue_push({yr, xr});
        int dx[] = {0, 0, -1, 1, -1, -1, 1, 1};
        int dy[] = {-1, 1, 0, 0, -1, 1, -1, 1};
        while(!queue_empty()) {
                pair<int, int> pos = queue_front();
                queue_pop();
                for(int i = 0; i < 8; i++) {
                        int x = pos.first + dx[i];
                        int y = pos.second + dy[i];
                        if(r[x][y] == 0) {
                                r[x][y] = r[pos.first][pos.second] + 1;
                                queue_push({x, y});
                        }
                }
        }
        int xx,yy;
        while(!queue_empty())
                queue_pop();
        jj[yj][xj] = 1;
        queue_push({yj, xj});
        while(!queue_empty()) {
                pair<int, int> pos = queue_front();
                queue_pop();
                for(int i = 0; i < 8; i++) {
                        int x = pos.first + dx[i];
                        int y = pos.second + dy[i];
                        if(jj[x][y] == 0) {
                                jj[x][y] = jj[pos.first][pos.second] + 1;
                                queue_push({x, y});
                        }
                }
        }
        for(int i=1; i<=n; i++) {
                for(int j=1; j<=m; j++) {
                        if(r[i][j]==jj[i][j]&&(r[i][j]>0)) {
                                if(minn>r[i][j]) {
                                        xx=i;
                                        yy=j;
                                        minn=r[i][j];
                                }
                        }
                }
        } /*
        for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++)
                        cout<<r[i][j]<<" ";
                cout<<'\n';
        }
        cout<<'\n';
        for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++)
                        cout<<jj[i][j]<<" ";
                cout<<'\n';
        } */
        cout<<minn<<" "<<xx<<" "<<yy;
        return 0;
}