Cod sursa(job #1204206)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 2 iulie 2014 12:43:46
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <fstream>
#include <string.h>
#define NMax 110
#define INF 2000000000
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int n, m, rx, ry, jx, jy, i, j, p, u, lmin=INF, cmin=INF, tmin=INF, cx, cy;
short int vizr[NMax][NMax], vizj[NMax][NMax], qu[2][NMax];
const int dx[]={0, 0, 1, 1, 1, 0, -1, -1, -1}, dy[]={0, -1, -1, 0, 1, 1, 1, 0, -1};
char mat[NMax][NMax], line[NMax];
int main()
{
    f>>n>>m;
    f.get();
    for (i=1; i<=n; i++) {
        f.get(line, NMax);
        for (j=0; j<m; j++) {
            if (line[j] == ' ')
                mat[i][j+1]=' ';
            else if(line[j] == 'X')
                mat[i][j+1]='X';
            else if(line[j]=='R') {
                mat[i][j+1]='R';
                rx=i, ry=j+1;
            }
            else if(line[j]=='J') {
                mat[i][j+1]='J';
                jx=i, jy=j+1;
            }
        }
        f.get();
    }
    vizr[rx][ry]=1;
    qu[0][1]=rx;
    qu[1][1]=ry;
    p=u=1;
    while (p<=u) {
        for (i=1; i<=8; i++) {
            int l=qu[0][p]+dx[i];
            int c=qu[1][p]+dy[i];
            if (mat[l][c]==' ' && vizr[l][c]==0 && l>=1 && l<=n && c>=1 && c<=m) {
                u++;
                qu[0][u]=l;
                qu[1][u]=c;
                vizr[l][c] = vizr[ qu[0][p] ][ qu[1][p] ] + 1;
            }
        }
        p++;
    }
    vizj[jx][jy]=1;
    memset(qu, 0, sizeof(qu));
    qu[0][1]=jx;
    qu[1][1]=jy;
    p=u=1;
    while (p<=u) {
        for (i=1; i<=8; i++) {
            int l=qu[0][p]+dx[i];
            int c=qu[1][p]+dy[i];
            if (mat[l][c]==' ' && vizj[l][c]==0 && l>=1 && l<=n && c>=1 && c<=m) {
                u++;
                qu[0][u]=l;
                qu[1][u]=c;
                vizj[l][c] = vizj[ qu[0][p] ][ qu[1][p] ] + 1;
            }
        }
        p++;
    }
    for (i=1; i<=n; i++) {
        for (j=1; j<=m; j++)
            g<<vizj[i][j];
        g<<"\n";
    }
    for (i=1; i<=n; i++) {
        for (j=1; j<=m; j++) {
            if (mat[i][j]==' ') {
                if (vizr[i][j] == vizj[i][j] && vizr[i][j]!=0) {
                    if (vizr[i][j]<tmin) {
                        tmin=vizr[i][j];
                        cx=i;
                        cy=j;
                    }
                    else if (vizr[i][j]==tmin) {
                        if (lmin > i) {
                            tmin=vizr[i][j];
                            cx=i;
                            cy=j;
                        }
                        else if(lmin==i) {
                            if (cmin > j) {
                                tmin=vizr[i][j];
                                cx=i;
                                cy=j;
                            }
                        }
                    }
                }

            }
        }
    }
    g<<tmin<<" "<<cx<<" "<<cy<<"\n";
    return 0;
}