# Woodstock Blog

## a tech blog for general algorithmic interview questions

### Solution

As for whether we choose to check each equipment position, or check each vacant position, it’s decided by how many equipment is there. If very little equipments (e is small), then this solution should work.

However, what is there is obstacles in the matrix?

We have to use BFS then. It took more space usage, but the time complexity should be same.

### Code

``````public void findCenter(int[][] input, int numberOfEquip) {
int m = input.length;
int n = input[0].length;

// there's gonna be m * n positions
// we gonna cumulate (numberOfEquip) distances for each position
int[] dis = new int[m * n];

// from the input map, find Equipments
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (input[i][j] == 1) {
// 1 represents equipment
// when found, add the distance to every position
cumulateDistance(i, j, dis, m, n);
}
}
}

// find the smallest cumulated distance from dis[].
int sIndex = 0;
int smallest = dis[0];
for (int i = 0; i < m * n; i++) {
if (dis[i] < smallest) {
smallest = dis[i];
sIndex = i;
}
}

// index sIndex is the final answer
System.out.println("Answer: " + (sIndex / n) + " " + (sIndex % n));
}

private void cumulateDistance(int x, int y, int[] dis, int m, int n) {
for (int i = 0; i < m * n; i++) {
int a = i / n;
int b = i % n;
dis[i] += Math.abs(a - x) + Math.abs(b - y);
}
}
``````