Cod sursa(job #1928135)

Utilizator robert_fanrRobert Banu robert_fanr Data 15 martie 2017 21:20:46
Problema Rj Scor 0
Compilator java Status done
Runda Arhiva de probleme Marime 5.37 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 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();
        }
         
        // The name of the file to open.
        String fileName = "rj.in";
 
        // This will reference one line at a time
        String line = null;
         
        short distRomeo[][] = new short[n][m];
        short distJulieta[][] = new short[n][m];
        
        Punct R = new Punct(), J = new Punct();
        
        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;
            short i=0;
            while((line = bufferedReader.readLine()) != null) {
                if (first) {
                    first = false;
                    continue;
                }
                char vector[] = line.toCharArray();
                for (short j=0; j<m; ++j) {
                    if (vector[j] == 'R') {
                        R.i = i;
                        R.j = j;
                    }
                    if (vector[j] == 'J') {
                        J.i = i;
                        J.j = j;
                    }
                    if (vector[j] == ' ') {
                        distRomeo[i][j]=Short.MAX_VALUE;
                        distJulieta[i][j]=Short.MAX_VALUE;
                    }
                }
                ++i;
            }
            // 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 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();
            short 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] = (short) (distRomeo[current.i][current.j] + 1);
                            q.add(vecin);
                        }
            }
        }
         
      //BFS Julieta
        q.clear();
        q.add(J);
        distJulieta[J.i][J.j] = 1;
         
        while (!q.isEmpty()) {
            Punct current = q.remove();
            short 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] = (short) (distJulieta[current.i][current.j] + 1);
                            q.add(vecin);
                        }
            }
        }
         
        short distMin = Short.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
        }
    }
}