[java] алгоритм для поиска наибольшей площади



Answers

Мне дали это задание в процессе собеседования, и это код компиляции и запуска

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class FindArea {
public static void main(String[] args) 
{
    String fileName="C:\\map.txt";
    FindArea area = new FindArea();
    try{
        FileReader inputFile = new FileReader(fileName);
        BufferedReader bufferReader = new BufferedReader(inputFile);

        char[][] twoArray= new char[100][100];
        String line;
        int i=0;

        while ((line = bufferReader.readLine()) != null) {
            twoArray[i] = line.toCharArray();
            System.out.println(line);
            i++;
        }
        bufferReader.close();

        System.out.println("file read");
        System.out.println("Max area: " + area.getMaxArea(twoArray));

    } catch(Exception e) {
        System.out.println("error : " + e.getMessage());
    }
}

/**
 * Get the maximum area from the given map
 * 
 * @param charArray
 * @return
 */
private int getMaxArea(char[][] charArray) {
    HashMap<Integer, ArrayList<String>> numberOfBoxes = convertToBoxes(charArray);

    numberOfBoxes = mergeOverlapAreas(numberOfBoxes);

    int largeSize = 0; 
    for (Integer key : numberOfBoxes.keySet()) {
        ArrayList<String> list = numberOfBoxes.get(key);
        System.out.println("Key : " + key + " Size : " + list.size());
        if (largeSize < list.size()) {
            largeSize = list.size();
        }
    }
    return largeSize;
}

/**
 * Convert the 2d Array to HashMap
 * Key being the count of boxes and 
 * Value being the list of indexes associations
 * 
 * @param charArray
 * @return
 */
private HashMap<Integer, ArrayList<String>> convertToBoxes(char[][] charArray) {
    HashMap<Integer, ArrayList<String>> numberOfBoxes = new HashMap<Integer, ArrayList<String>>();
    int boxes = 0;

    for(int i=1; i<charArray.length; i++) {

        for (int j=0; j<charArray[i].length; j++) {

            if (charArray[i][j] == '.') {

                boolean isExists = false;

                for(Integer key : numberOfBoxes.keySet()) {

                    ArrayList<String> arrList = numberOfBoxes.get(key);

                    if(arrList != null) {

                        if(arrList.contains((i-1) + "-" + j) ||
                           arrList.contains(i + "-" + (j-1))) {

                            isExists = true;
                            arrList.add(i + "-" + j);
                            numberOfBoxes.put(key, arrList);
                        }
                    } 
                }

                if (!isExists) {
                    ArrayList<String> list = new ArrayList<String>();
                    list.add(i + "-" + j);
                    numberOfBoxes.put(boxes, list);
                    boxes++;
                }
            }
        }
    }
    return numberOfBoxes;
}

/**
 * Check for the points exists in more than one area
 * @param numberOfBoxes
 * @return
 */
private  HashMap<Integer, ArrayList<String>> mergeOverlapAreas( HashMap<Integer, ArrayList<String>> numberOfBoxes) {

    for(Integer key : numberOfBoxes.keySet()) {
        ArrayList<String> list1 = numberOfBoxes.get(key);

        for (Integer key2 : numberOfBoxes.keySet()) {

            if (key < key2) {

                ArrayList<String> list2 = numberOfBoxes.get(key2);
                Iterator<String> listIter = list2.iterator();

                while(listIter.hasNext()) {

                    if (list1.contains(listIter.next())) {
                        list1.addAll(list2);
                        Set<String> noDuplicates = new HashSet<String>(list1);
                        numberOfBoxes.put(key, new ArrayList<String>(noDuplicates));
                        break;
                    }
                }
            }
        }

    }
    return numberOfBoxes;
}

}
Question
................................
.XXXXXXXXXXXXXXX.....XXXXXXXXXX.
.X.....X.......X.....X........X.
.X.....X.......XXXXXXX........X.
.XXXXXXXXXXXX.................X.
.X....X.....X.................X.
.X....X.....XXXX..............X.
.XXXXXX........X..............X.
......X........X..............X.
......X........X..............X.
......X........X..............X.
......XXXXXXXXXXXXXXXXXXXXXXXXX.
................................

Ищете алгоритм для поиска наибольшей площади. Здесь «площадь» определяется как количество точек (.), Ограниченных Xs.

   private static void readFile(File inputFile) throws IOException {

    Scanner fileScanner = new Scanner(inputFile);

    Point previousPoint = null;

    int rowCount = 0;
    while(fileScanner.hasNext()){
        String line = fileScanner.next();

        String[] points = line.split(" ");

        for(int columnCount=0;columnCount<points.length;columnCount++){

            if(points[columnCount].equalsIgnoreCase("x")){
                Point currentPoint = new Point();
                currentPoint.setxValue(columnCount);
                currentPoint.setyValue(rowCount);
            }
        }

        rowCount++;
    }
  }

Это мое первое и изо всех сил пытаюсь двигаться дальше.






Links