Pagini recente » Cod sursa (job #1187384) | Cod sursa (job #2180041) | Cod sursa (job #1825588) | Cod sursa (job #3127041) | Cod sursa (job #1927166)
//package rj;
import java.io.*;
import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
class Punct{
public int i;
public int j;
public Punct() {};
public Punct (int i1, int j1) {
i = i1;
j = j1;
}
}
public class Main {
private static Scanner scanner;
//private static FileInputStream scanner;
public static void main(String[] args) {
int n=0,m=0;
try {
//scanner = new BufferedReader(new FileReader("rj.in"));
scanner = new Scanner(new BufferedReader(new FileReader("rj.in")));
n = scanner.nextInt();
m = scanner.nextInt();
} catch (FileNotFoundException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
char matrice[][] = new char[n][m];
// The name of the file to open.
String fileName = "rj.in";
// This will reference one line at a time
String line = null;
try {
// FileReader reads text files in the default encoding.
FileReader fileReader =
new FileReader(fileName);
// Always wrap FileReader in BufferedReader.
BufferedReader bufferedReader =
new BufferedReader(fileReader);
boolean first=true;
int i=0;
while((line = bufferedReader.readLine()) != null) {
if (first) {
first = false;
continue;
}
matrice[i++] = line.toCharArray();
}
// Always close files.
bufferedReader.close();
}
catch(FileNotFoundException ex) {
System.out.println(
"Unable to open file '" +
fileName + "'");
}
catch(IOException ex) {
System.out.println(
"Error reading file '"
+ fileName + "'");
// Or we could just do this:
// ex.printStackTrace();
}
byte distRomeo[][] = new byte[n][m];
byte distJulieta[][] = new byte[n][m];
Punct R = new Punct(), J = new Punct();
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j) {
if (matrice[i][j] == 'R') {
R.i = i;
R.j = j;
}
if (matrice[i][j] == 'J') {
J.i = i;
J.j = j;
}
if (matrice[i][j] == ' ') {
distRomeo[i][j]=Byte.MAX_VALUE;
distJulieta[i][j]=Byte.MAX_VALUE;
}
}
int iDirectie[] = {-1, -1, -1, 0, 1, 1, 1, 0 };
int jDirectie[] = {-1, 0, 1, 1, 1, 0, -1, -1 };
//BFS Romeo
Queue <Punct> q = new LinkedList<Punct>();
q.add(R);
distRomeo[R.i][R.j]=1;
while (!q.isEmpty()) {
Punct current = q.remove();
int k;
for (k=0; k<8; ++k) {
Punct vecin = new Punct(current.i+iDirectie[k],current.j+jDirectie[k]);
if (vecin.i>=0 && vecin.i<n)
if (vecin.j>=0 && vecin.j<m)
if (distRomeo[vecin.i][vecin.j] > distRomeo[current.i][current.j] + 1) {
distRomeo[vecin.i][vecin.j] = (byte) (distRomeo[current.i][current.j] + 1);
q.add(vecin);
}
}
}
//BFS Julieta
Queue <Punct> q2 = new LinkedList<Punct>();
q2.add(J);
distJulieta[J.i][J.j] = 1;
while (!q2.isEmpty()) {
Punct current = q2.remove();
int k;
for (k=0; k<8; ++k) {
Punct vecin = new Punct(current.i+iDirectie[k],current.j+jDirectie[k]);
if (vecin.i>=0 && vecin.i<n)
if (vecin.j>=0 && vecin.j<m)
if (distJulieta[vecin.i][vecin.j] > distJulieta[current.i][current.j] + 1) {
distJulieta[vecin.i][vecin.j] = (byte) (distJulieta[current.i][current.j] + 1);
q2.add(vecin);
}
}
}
int distMin = Integer.MAX_VALUE;
Punct punctIntalnire = new Punct();
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j) {
if (distRomeo[i][j] != 0)
if (distRomeo[i][j] == distJulieta[i][j])
if (distRomeo[i][j] < distMin) {
distMin = distRomeo[i][j];
punctIntalnire.i = i+1;
punctIntalnire.j = j+1;
}
}
try {
PrintWriter writer = new PrintWriter("rj.out");
writer.print(distMin);
writer.print(" ");
writer.print(punctIntalnire.i);
writer.print(" ");
writer.print(punctIntalnire.j);
writer.close();
}
catch (IOException e) {
//eroare
}
}
}