В двумерной сетке каждая ячейка представляет собой либо зомби, либо человека. Зомби могут каждый день превращать соседние (сверху/вниз/влево/вправо) людей в зомби. Узнайте, сколько дней нужно, чтобы заразить всех людей?
Входные данные:
матрица, массив двумерных целых чисел, где a[i][j] = 1 представляет собой зомби в ячейке, а a[i][j] = 0 представляет человека в ячейке.
Вывод:
Возвратите целое число, указывающее, сколько дней потребуется, чтобы заразить всех людей.
Возвратите -1, если зомби не существует.
Пример:
Ввод:
[[0, 1, 1, 0, 1],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 1],
[0, 1, 0, 0, 0]]
Выход:
2
Объяснение:
В конце дня 1 состояние сетки:
[[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[0, 1, 0, 1, 1],
[1, 1, 1, 0, 1]]
В конце дня 2 состояние сетки:
[[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
> [1, 1, 1, 1, 1],
[1, 1, 1, 1, 1]]
Решение :-
импортировать java.util.LinkedList;
импортировать java.util.Queue;
открытый класс ZombiMatrix {
public static void main(String[] args) {
узел класса {
внутренний ряд;
внутренний столбец;
публичный узел (int i, int j) {
ряд = я;
столбец = j;
}
}
час = -1;
//влево/вправо/вверх/вниз
int direction[][] = {{0,-1}, {-1, 0}, {1,0}, {0,1}};
Queue‹Node› queue = new LinkedList‹Node›();
матрица int[][] = {{0, 1, 1, 0, 1},
{0, 1, 0, 1, 0},
{0, 0, 0, 0, 1},
{0, 1, 0, 0, 0}};
for (int i = 0; i ‹ matrix.length; i++) {
for (int j = 0; j ‹ matrix[0].length; j++) {
если (матрица [я] [j] == 1) {
queue.add (новый узел (i, j));
}
}
}
пока(!queue.isEmpty()) {
int InitialSize = очередь.размер();
for (int i = 1; i ‹= initialSize; i++) {
Узел tempNode = queue.poll();
for(int[] dir: направление) {
int x = tempNode.row + dir[0];
int y = tempNode.column + dir[1];
if(x ›= 0 && x ‹ matrix.length
&& y ›= 0 && y ‹ matrix[0].length
&& матрица[x][y] == 0) {
матрица[х][у] = 1;
queue.add (новый узел (x, y));
}
}
}
час++;
}
System.out.println(час); //вернуть час;
}
}
