Cod sursa(job #879766)

Utilizator thebest001Neagu Rares Florian thebest001 Data 15 februarie 2013 21:01:11
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <stdio.h>
#include <queue>
using namespace std;

bool walls[101][101];
short RV[101][101],JV[101][101];
struct movement{int x,y;};

queue<movement> R,J;

int MIN=100001,MINX,MINY;

char dx[]={1,0,-1,0,1,-1,-1,1};
char dy[]={0,1,0,-1,1,-1,1,-1};

void RMOVE(){
    while (!R.empty()){
        movement n=R.front();
        for (int i=0;i<8;i++){
            if (!RV[n.x+dx[i]][n.y+dy[i]] && walls[n.x+dx[i]][n.y+dy[i]]){
                RV[n.x+dx[i]][n.y+dy[i]]=RV[n.x][n.y]+1;
                movement next;
                next.x=n.x+dx[i];
                next.y=n.y+dy[i];
                R.push(next);
            }
        }
        R.pop();
    }
}

void JMOVE(){
    while (!J.empty()){
        movement n=J.front();
        for (int i=0;i<8;i++){
            if (!JV[n.x+dx[i]][n.y+dy[i]] && walls[n.x+dx[i]][n.y+dy[i]]){
                JV[n.x+dx[i]][n.y+dy[i]]=JV[n.x][n.y]+1;
                movement next;
                next.x=n.x+dx[i];
                next.y=n.y+dy[i];
                if (JV[n.x+dx[i]][n.y+dy[i]]==RV[n.x+dx[i]][n.y+dy[i]]){
                    int numar=JV[n.x+dx[i]][n.y+dy[i]]+1;
                    if (MIN>numar){
                        MIN=numar;
                        MINX=n.x+dx[i];
                        MINY=n.y+dy[i];
                    }
                    if (MIN==numar){
                        if (MINX>n.x+dx[i]){
                            MINX=n.x+dx[i];
                            MINY=n.y+dy[i];
                        }
                    }
                }
                J.push(next);
            }
        }
        J.pop();
    }

}

int main(){
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);

    int n,m;
    scanf("%d %d\n",&n,&m);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            char c;
            scanf("%c",&c);
            if (c==' ') walls[i][j]=true;
            if (c=='R') {movement x;x.x=i;x.y=j;R.push(x);}
            if (c=='J') {movement x;x.x=i;x.y=j;J.push(x);}
        }
        scanf("\n");
    }
    RMOVE();
    JMOVE();
    printf("%d %d %d",MIN,MINX,MINY);
    return 0;
}