Cod sursa(job #1927105)

Utilizator robert_fanrRobert Banu robert_fanr Data 14 martie 2017 22:17:30
Problema Rj Scor 0
Compilator java Status done
Runda Arhiva de probleme Marime 4.62 kb
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 Rj {

	private static Scanner scanner;

	public static void main(String[] args) throws IOException {

		int n,m;
		
		scanner = new Scanner(new File("rj.in"));
		n = scanner.nextInt();
		m = scanner.nextInt();
		
		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();
        }
        
        int distRomeo[][] = new int[n][m];
        int distJulieta[][] = new int[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]=Integer.MAX_VALUE;
        			distJulieta[i][j]=Integer.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] = 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] = 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
        }
	}
}