Cod sursa(job #1204235)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 2 iulie 2014 13:57:29
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <fstream>
#include <string.h>
#define NMax 105
#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*NMax], mat[NMax][NMax];
const int dx[]={0, 0, 1, 1, 1, 0, -1, -1, -1}, dy[]={0, -1, -1, 0, 1, 1, 1, 0, -1};
char line[150];
int main()
{
    f>>n>>m;
    f.getline(line, 140);
    for (i=1; i<=n; i++) {
        f.getline(line, 140);
        for (j=0; j<m; j++) {
            if (line[j] == ' ')
                mat[i][j+1]=0;
            else if(line[j] == 'X')
                mat[i][j+1]=1;
            else if(line[j]=='R') {
                rx=i, ry=j+1;
            }
            else if(line[j]=='J') {
                jx=i, jy=j+1;
            }
        }
    }
    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]==0 && 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]==0 && 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++) {
            if (mat[i][j]==0) {
                if (vizr[i][j] == vizj[i][j] && vizr[i][j]!=0) {
                    if (vizr[i][j]<tmin) {
                        tmin=vizr[i][j];
                        cx=i;
                        cy=j;
                        lmin=i;
                        cmin=j;
                    }
                    else if (vizr[i][j]==tmin) {
                        if (lmin > i) {
                            tmin=vizr[i][j];
                            cx=i;
                            cy=j;
                            lmin=i;
                        }
                        else if(lmin==i) {
                            if (cmin > j) {
                                tmin=vizr[i][j];
                                cx=i;
                                cy=j;
                                cmin=j;
                            }
                        }
                    }
                }
                
            }
        }
    }
    g<<tmin<<" "<<cx<<" "<<cy<<"\n";
    return 0;
}