Если вам разрешено обновлять grid, используйте grid.get(y).get(x) для проверки сетки и grid.get(y).set(x, value) для обновления сетки. Если вам не разрешено обновлять сетку, начните с копирования значений в int[][] 2D-массив, затем используйте это вместо этого в приведенном ниже решении.
Сканируйте сетку на наличие 0 значений и добавьтекоординаты Queue<Point>, например ArrayDeque<Point>, где Point - это объект с двумя int полями, например, java.awt.Point класс.
Мы делаем эточтобы обеспечить хорошую производительность, при сложности выполнения, например, O (нм) , где n и m - ширина и высота сетки.
Запустите цикл с i = 1. В цикле итерируйте очередь. Если точка имеет соседнее значение, равное i, установите значение точки на i + 1, в противном случае добавьте точку во вторую очередь. В конце замените первую очередь на вторую, увеличьте i на 1 и делайте это снова, пока очередь не станет пустой.
В результате получается последовательность 2D-матриц, подобная этой:
0 1 1 0 1 → 2 1 1 2 1 → 2 1 1 2 1 → 2 1 1 2 1
0 1 0 0 0 → 2 1 2 0 2 → 2 1 2 3 2 → 2 1 2 3 2
0 0 0 0 1 → 0 2 0 2 1 → 3 2 3 2 1 → 3 2 3 2 1
0 0 0 1 0 → 0 0 2 1 2 → 0 3 2 1 2 → 4 3 2 1 2
Самое высокое значение в матрице - 4, поэтому ответ - 3 часа, на одно меньше, чем самое высокое значение.
ОБНОВЛЕНИЕ
Вот код, который копирует входные данные в двумерный массив и понижает значения на 1, так как это имеет больше смысла.
static int hours(int rows, int columns, List<List<Integer>> grid) {
// Build hourGrid, where value is the number of hours until the
// node can send, with MAX_VALUE meaning the node cannot send.
// Also build queue of nodes that cannot send.
int[][] hourGrid = new int[rows][columns];
Queue<Point> pending = new ArrayDeque<>();
for (int y = 0; y < rows; y++) {
for (int x = 0; x < columns; x++) {
if (grid.get(y).get(x) == 0) {
hourGrid[y][x] = Integer.MAX_VALUE;
pending.add(new Point(x, y));
}
}
}
// Keep iterating the queue until all pending nodes can send.
// Each iteration adds 1 hour to the total time.
int hours = 0;
for (; ! pending.isEmpty(); hours++) {
// Check all pending nodes if they can receive data
Queue<Point> notYet = new ArrayDeque<>();
for (Point p : pending) {
if ((p.x > 0 && hourGrid[p.y][p.x - 1] <= hours)
|| (p.x < columns - 1 && hourGrid[p.y][p.x + 1] <= hours)
|| (p.y > 0 && hourGrid[p.y - 1][p.x] <= hours)
|| (p.y < rows - 1 && hourGrid[p.y + 1][p.x] <= hours)) {
// Node can receive from a neighbor, so will be able to send in 1 hour
hourGrid[p.y][p.x] = hours + 1;
} else {
// Not receiving yet, so add to queue for next round
notYet.add(p);
}
}
pending = notYet;
}
return hours;
}
Для тестирования, построения List<List<Integer>> и отправкив отдельных rows и columns значениях громоздко, поэтому вот вспомогательный метод:
static int hours(int[][] grid) {
final int rows = grid.length;
final int columns = grid[0].length;
List<List<Integer>> gridList = new ArrayList<>(rows);
for (int[] row : grid) {
List<Integer> rowList = new ArrayList<>(columns);
for (int value : row)
rowList.add(value); // autoboxes
gridList.add(rowList);
}
return hours(rows, columns, gridList);
}
Тест
System.out.println(hours(new int[][] { // data from question
{ 0, 1, 1, 0, 1 },
{ 0, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 1 },
{ 0, 1, 0, 0, 0 },
}));
System.out.println(hours(new int[][] { // data from answer
{ 0, 1, 1, 0, 1 },
{ 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1 },
{ 0, 0, 0, 1, 0 },
}));
Вывод
2
3