I’m working on this problem from the 2019 January Silver contest, Icy Perimeter. My solution, which is in Java, passes on the first ten test cases, at 2.8 seconds max (for the tenth case) but times out on the eleventh. I looked at the solution and could not determine any obvious difference in it compared to mine – my code essentially just runs through each cell, doing a flood fill to find the area when it comes across an ice cream cell not already visited, while also keeping track of the perimeter. It updates the largest area blob and the corresponding perimeter as it goes and then outputs the final answer once all is said and done. What am I missing - is there some sort of Java optimization I should do to get that last test case, or is there a flaw in my code I haven’t identified? Thank you!
My code is below - I’m also new to Java, having only started learning a few weeks ago, so if some parts are clunky or not the most efficient way of doing something, I apologize!
code
import java.io.*;
import java.util.*;
import java.lang.Math;
public class icyPerimeter {
// declare variables to use in solving
public static String[][] grid;
public static boolean[][] visited;
public static int N;
// main function
public static void main(String[] args) throws IOException {
// read in data
FileInputStream in = new FileInputStream("perimeter.in");
FileWriter out = new FileWriter("perimeter.out");
BufferedReader input = new BufferedReader (new InputStreamReader(in));
N = Integer.parseInt(input.readLine());
grid = new String[N][N];
visited = new boolean[N][N];
for (int i=0; i<N; i++) {
String[] row = input.readLine().split("");
for (int j=0; j<N; j++) grid[i][j] = row[j]; }
// solve by going through each cell of grid
int bestArea = 0;
int bestPerimeter = 0;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
// if we come upon an ice-cream cell we haven't previously visited
if (grid[i][j].equals("#") && !visited[i][j]) {
// find area and perimeter of blob containing given cell
int[] blobProperties = find_blob(i,j);
int area = blobProperties[0];
int perimeter = blobProperties[1];
// update area and perimeter according to rules in problem
if (area > bestArea) {
bestArea = area;
bestPerimeter = perimeter; }
else if (area == bestArea) {
bestPerimeter = Math.min(perimeter, bestPerimeter); }
}
}
}
// write result
out.write(bestArea + " " + bestPerimeter);
in.close();
out.close();
}
public static int[] find_blob(int i, int j) {
// finds area and perimeter of the blob cell (i,j) is part of
/* variable set up - create set for blob, set up queue,
mark original cell as visited */
visited[i][j] = true;
HashSet<int[]> blob = new HashSet<>();
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {i, j});
ArrayList<int[]> directions = new ArrayList<>();
directions.add(new int[] {0,1});
directions.add(new int[] {1,0});
directions.add(new int[] {0,-1});
directions.add(new int[] {-1,0});
HashSet<int[]> surrounding = new HashSet<>();
// floodfill-dfs to find blob
while (!queue.isEmpty()) {
int[] current = queue.poll();
blob.add(current);
for (int[] d: directions) { // go through every location to right/left/above/below the given cell
int[] newLoc = new int[] {current[0]+d[0], current[1] + d[1]};
if (valid(newLoc[0], newLoc[1]) && !visited[newLoc[0]][newLoc[1]] && grid[newLoc[0]][newLoc[1]].equals("#")) {
queue.add(newLoc);
visited[newLoc[0]][newLoc[1]] = true; }
else if (!valid(newLoc[0], newLoc[1]) || !visited[newLoc[0]][newLoc[1]]) surrounding.add(newLoc); // cells that aren't ice cream cells are surrounding the blob, meaning they count towards the perimeter
}
}
// return area and perimeter
int area = blob.size();
int perimeter = surrounding.size();
return new int[] {area, perimeter};
}
static boolean valid(int i, int j) {
// function to check if given cell (i,j) is within grid
return 0<=i && i<N && 0<=j && j<N;
}
}