Cod sursa(job #1588273)

Utilizator Hilbert_DennisHilbert Dennis Hilbert_Dennis Data 2 februarie 2016 22:16:45
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <iomanip>
#include <string>
using namespace std;

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

int n, m, i, ok, aux, nr, r[102][102], j[102][102], x1, y1, x2, y2, x, y, timp, k, l[102][102];
char c;
int dl[8]={0, 1, 0, -1, -1, 1, -1, 1};
int dc[8]={1, 0, -1, 0, -1, 1,  1,-1};

void parcurge (int x, int y, int d[102][102]) {
struct Punct {
    int l, c;
} C[10404], p;
int inc=0, sf=0, i;
for (i=0; i<=n+1; i++)
    for (k=0; k<=m+1; k++) d[i][k]=-1;
C[0].l=x; C[0].c=y; d[x][y]=1;
while (inc<=sf) {
     p=C[inc++];
     for (i=0; i<=7; i++)
        if (l[p.l+dl[i]][p.c+dc[i]]==' ' && d[p.l+dl[i]][p.c+dc[i]]==-1) {
            d[p.l+dl[i]][p.c+dc[i]]=1+d[p.l][p.c];
            C[++sf].l=p.l+dl[i];
            C[sf].c=p.c+dc[i];
        }
    }
}
int main() {
fin>>n>>m;
for (i=0; i<=n+1; i++) l[i][0]=l[i][m+1]='X';
for (i=0; i<=m+1; i++) l[0][i]=l[n+1][i]='X';
fin.get(c);
for (i=1; i<=n; i++)
    {for (k=1; k<=m; k++) {
      fin.get(c); l[i][k]=c;
         if (l[i][k]=='R') {
        x1=i;
        y1=k;
        l[i][k]=' ';
      }
         if (l[i][k]=='J') {
        x2=i;
        y2=k;
        l[i][k]=' ';
      }
        }
    fin.get(c);}

    for(i = 0; i <= n + 1; i++) {
        r[i][0] = -1;
        r[i][m + 1] = -1;
        j[i][0] = -1;
        j[i][m + 1] = -1;
    }
    for(k = 0; k <= m + 1; k++) {
        r[0][k] = -1;
        r[n + 1][k] = -1;
        j[0][k] = -1;
        j[n + 1][k] = -1;
    }
    parcurge(x1, y1, r);
    parcurge(x2, y2, j);
    timp = (r[x2][y2] - 1) / 2;
    timp = 10000;
    for(i = 1; i <= n; i++) {
        for(k = 1; k <= m; k++)
            if(r[i][k] == j[i][k] and r[i][k] != -1) {
                if(r[i][k] < timp) {
                    timp = r[i][k];
                    x = i;
                    y = k;

                }
            }
    }

    fout << timp << " " << x << " " << y;

return 0;
}