Cod sursa(job #357446)
Utilizator | Data | 19 octombrie 2009 12:09:43 | |
---|---|---|---|
Problema | Rj | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 13.72 kb |
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#include <algorithm>
using namespace std;
int BFS(int start, int end);
list<int>G[10000];
int loc;
int main() {
fstream f1, f2;
int n, m, i, j, k, l, c, nl, nc, startr, startj, julieta, romeo, min=10000;
int dl[]={-1, -1, -1, 0, 0, 1, 1, 1};
int dc[]={-1, 0, 1, -1, 1, -1, 0, 1};
char v[10000], aux;
f1.open("rj.in", ios::in);
f1>>n>>m;
aux=f1.get();
for(i=1; i<=n; i++) {
for(j=1; j<=m; j++) {
k=(i-1)*n+j;
v[k]=f1.get();
}
aux=f1.get();
}
f1.close();
//daca v[i] si " " sunt egale: if(!strcmp(v[i], " "))
for(i=1; i<=n*m; i++) {
if(i%n==0) { l=i/n-1; }
else { l=i/n; }
if(i%m==0) { c=m; }
else { c=i%n; }
if(v[i]=='R') {
startr=i;
}
if(v[i]=='J') {
startj=i;
}
if(v[i]!='X') {
//(l-1, c-1), (l-1, c), (l-1, c+1)
//(l, c-1), (l, c+1)
//(l+1, c-1), (l+1, c), (l+1, c+1)
if(i==1) {
k=i+1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i+m;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i+m+1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
}
else if(i==m) {
k=i-1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i+m-1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i+m;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
}
else if(i==n*m) {
k=i-1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i-m;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i-m-1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
}
else if(i==(n-1)*m+1) {
k=i+1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i-m;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i-m+1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
}
else if(i<m) {
k=i-1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i+m-1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i+m;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i+1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i+m+1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
}
else if(i>(n-1)*m) {
k=i-m-1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i-m;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i-m+1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i-1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i+1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
}
else if(i%m==0) {
k=i-1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i+m-1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i+m;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i-m-1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i-m;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
}
else if(i%m==1) {
k=i-c;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i-c+1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i+1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i+c;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
k=i+c+1;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
}
else {
for(j=0; j<8; j++) {
nl=l+dl[j];
nc=c+dc[j];
k=nl*n+nc;
if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
//nodul i si nodul k au muchie comuna
G[i].push_back(k);
}
}
}
}
}
for(i=1; i<=n*m; i++) {
//startr = casa lui romeo
//startj = casa julietei
if(!G[i].empty()) {
romeo=BFS(i, startr);
julieta=BFS(i, startj);
if(romeo==julieta) { if(romeo<min) { min=romeo; loc=i; } }
}
}
if(loc%n==0) { l=loc/n; }
else { l=loc/n+1; }
if(loc%m==0) { c=m; }
else { c=loc%n; }
//l, c
f2.open("rj.out", ios::out);
f2<<min<<" "<<l<<" "<<c<<endl;
f2.close();
return 0;
}
int BFS(int start, int end) {
int v[10000], cost[10000];
queue<int> c;
int p;
for(int i=1; i<=10000; i++) {
v[i]=0;
}
cost[start]=1;
c.push(start);
while(!c.empty()) {
p=c.front();
for(list<int>::iterator it=G[p].begin();it!=G[p].end();it++) {
if(!v[(*it)]) {
v[(*it)]=1;
cost[(*it)]=cost[p]+1;
if(*it==end) {
return cost[(*it)];
}
c.push(*it);
}
}
c.pop();
}
}