(UVA) Word Transformation - Solution 2

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=676&page=show_problem&problem=370

The solution below used Floyd-Warshall to solve this problem. If you want to see another solution using Breadth-First Search, click here.


import java.io.*;
import java.util.*;

class Main {
    public ArrayList<String> mapIntToString;
    public Map<String, Integer> mapStringToInt;
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numTests = Integer.parseInt(br.readLine());
        br.readLine();
        for (int test = 0; test < numTests; test++) {
            if (test > 0) {
                bw.write("\n"); // blank line between outputs
            }
           
            int index = 0;
            mapIntToString = new ArrayList<>();
            mapStringToInt = new HashMap<>();
            String word = br.readLine();
            while (!word.equals("*")) {
                mapIntToString.add(word);
                mapStringToInt.put(word, index++);
                word = br.readLine();
            }
            int[][] matrix = new int[index][index];
           
            for (int i = 0; i < index; i++) {
                for (int j = 0; j < index; j++) {
                    if (i == j || mapIntToString.get(i).length() != mapIntToString.get(j).length()) {
                        matrix[i][j] = Integer.MAX_VALUE/2;
                        continue;
                    }
                    int countDiff = 0;
                    for (int k = 0; k < mapIntToString.get(i).length(); k++) {
                        if (mapIntToString.get(i).charAt(k) != mapIntToString.get(j).charAt(k)) {
                            countDiff++;
                        }
                    }
                    matrix[i][j] = (countDiff == 1) ? (countDiff) : (matrix[i][j] = Integer.MAX_VALUE/2);
                }
            }         
           
            for (int i = 0; i < index; i++) {
                for (int j = 0; j < index; j++) {
                    for (int k = 0; k < index; k++) {
                        matrix[j][k] = Math.min(matrix[j][k], matrix[j][i]+matrix[i][k]);
                    }
                }
            }
           
            String line = br.readLine();
            while (line != null && !line.equals("")) {
                String[] s = line.split(" ");
                int start = mapStringToInt.get(s[0]);
                int end = mapStringToInt.get(s[1]);
                bw.write(s[0]+" "+s[1]+" "+matrix[start][end]+"\n");
                line = br.readLine();
            }
        }
                                                              
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução