Cod sursa(job #865212)

Utilizator 2dorTudor Ciurca 2dor Data 26 ianuarie 2013 11:21:48
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

int i, j, n, m, xx, yy, dist, lung;
int townr[105][105], townj[105][105];
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
char c;
bool found = false;
string s;

struct pnt {
    int x, y;
}aux_r, pkt_r, aux_j, pkt_j;

queue<pnt> romeo, julieta;

void border() {
    for (i = 0; i <= n + 1; ++i)
        townr[i][0] = townr[i][m + 1] = townj[i][0] = townj[i][m + 1] = -1;
    for (j = 0; j <= m + 1; ++j)
        townr[0][j] = townr[n + 1][j] = townj[0][j] = townj[n + 1][j] = -1;
}

inline void read() {
    fin >> n >> m; getline(fin, s);
    for (i = 1; i <= n; ++i) {
        getline(fin, s);
        lung = s.length();
        for (j = 0; j <= lung; ++j) {
            if (s[j] == 'X') townr[i][j + 1] = townj[i][j + 1] = -1;
            if (s[j] == 'R') { pkt_r.x = i; pkt_r.y = j + 1; romeo.push(pkt_r);}
            if (s[j] == 'J') { pkt_j.x = i; pkt_j.y = j + 1; julieta.push(pkt_j);}
            if (s[j] == ' ') townr[i][j + 1] = townj[i][j + 1] = 400;
        }
    }
    fin.close();
}

inline void go() {
    do {
        pkt_j = julieta.front();
        pkt_r = romeo.front();
        julieta.pop();
        romeo.pop();
        for (i = 0; i < 8; ++i) {
            aux_j.x = pkt_j.x + dx[i];
            aux_j.y = pkt_j.y + dy[i];
            aux_r.x = pkt_r.x + dx[i];
            aux_r.y = pkt_r.y + dy[i];
            if (townr[aux_r.x][aux_r.y] > townr[pkt_r.x][pkt_r.y] + 1 && townr[aux_r.x][aux_r.y] != -1) {
                townr[aux_r.x][aux_r.y] = townr[pkt_r.x][pkt_r.y] + 1;
                if (townr[aux_r.x][aux_r.y] == townj[aux_r.x][aux_r.y]) {
                    found = true;
                    xx = aux_r.x;
                    yy = aux_r.y;
                    dist = townr[aux_r.x][aux_r.y];
                    break;
                }else
                    romeo.push(aux_r);
            }
            if (townj[aux_j.x][aux_j.y] > townj[pkt_j.x][pkt_j.y] + 1 && townj[aux_j.x][aux_j.y] != -1) {
                townj[aux_j.x][aux_j.y] = townj[pkt_j.x][pkt_j.y] + 1;
                if (townj[aux_j.x][aux_j.y] == townr[aux_j.x][aux_j.y]) {
                    found = true;
                    xx = aux_j.x;
                    yy = aux_j.y;
                    dist = townj[aux_j.x][aux_j.y];
                    break;
                }else
                    julieta.push(aux_j);
            }
        }
    }while(!found);
}

void write() {
    if (townr[xx][yy - 1] == townj[xx][yy - 1])
        fout << dist + 1 << ' ' << xx << ' ' << yy - 1;
    else fout << dist + 1 << ' ' << xx << ' ' << yy - 1;
    fout.close();
}

int main() {
    read();
    border();
    go();
    write();
    return 0;
}