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;
}
} else {
for (int code : frontiers.get(i)) {
int r = code / n;
int c = code % n;
a[r][c] = 1;
}
}
}
}
return totalWalls;
}
static void dfs(int r, int c, int[][] a, int m, int n, boolean[][] visited,
Set<Integer> region, Set<Integer> frontier, int[] walls) {
visited[r][c] = true;
region.add(r * n + c);
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
if (a[nr][nc] == 1 && !visited[nr][nc]) {
dfs(nr, nc, a, m, n, visited, region, frontier, walls);
} else if (a[nr][nc] == 0) {
walls[0]++;
frontier.add(nr * n + nc);
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int[][] a = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = sc.nextInt();
}
}
System.out.print(minNumOfwalls(a, m, n));
}
}
FLIPKART ✅
q4
621 ·