Deloitte | COGNIZANT | IBM | CAPGEMINI
import java.io.*;
import java.util.*;
public class TestClass {
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
static int minNumOfwalls(int[][] a, int m, int n) {
int totalWalls = 0;
while (true) {
boolean[][] visited = new boolean[m][n];
List<Set<Integer>> regions = new ArrayList<>();
List<Set<Integer>> frontiers = new ArrayList<>();
List<Integer> wallsNeeded = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 1 && !visited[i][j]) {
Set<Integer> region = new HashSet<>();
Set<Integer> frontier = new HashSet<>();
int[] walls = new int[1];
dfs(i, j, a, m, n, visited, region, frontier, walls);
regions.add(region);
frontiers.add(frontier);
wallsNeeded.add(walls[0]);
}
}
}
if (regions.isEmpty()) {
break;
}
int maxFrontierIdx = -1;
int maxFrontierSize = -1;
for (int i = 0; i < frontiers.size(); i++) {
if (frontiers.get(i).size() > maxFrontierSize) {
maxFrontierSize = frontiers.get(i).size();
maxFrontierIdx = i;
}
}
if (maxFrontierSize == 0) {
break;
}
totalWalls += wallsNeeded.get(maxFrontierIdx);
for (int i = 0; i < regions.size(); i++) {
if (i == maxFrontierIdx) {
for (int code : regions.get(i)) {
int r = code / n;
int c = code % n;
a[r][c] = -1;
}
}
621 ·