PS: Не прокручивайте страницу, если вы ищете что-либо, связанное с новостями о covid19, это сообщение не попадает в какие-либо данные или новости, связанные со вспышкой!
Это я, нормализуя кодирование как проблему, чтобы определить, насколько важно социальное дистанцирование, даже если распространение всего четырехстороннее.
Вот проблема -
В гипотетическом мире, где все люди могут стоять в сетке m * n и в любой день, человеческая сетка может иметь следующие значения в ячейке:
Значение
0: ячейка пуста
Значение
1: человек не заражен
Значение
-1: человек заражен
Каждый день незараженный человек может заразить своего соседа в четырех направлениях (вверх / вниз / влево / вправо).
Нам нужно найти количество дней, которые пройдут, чтобы все люди в человеческой сети были инфицированы. Если это невозможно, мы должны вернуть -1.
Например, следующая человеческая сетка -
На то, чтобы затронуть всех, потребуется 18 дней!
Вот решение, которое принимает человеческую сетку в качестве входных данных и возвращает количество дней:
/****
* Assuming the humans can stand in a grid of some mXn
* @param humans
* @return
*/
public int infectedHumans(int[][] humans) {
if(null == humans || humans.length == 0){
return 0;
}
int rows = humans.length;
int cols = humans[0].length;
/***
* We will use infectedHumans queue to do the BFS
*/
Queue<int[]> infectedHumans = new LinkedList<>();
int nonInfectedHumans = 0;
// put the current state
for(int i = 0 ; i < rows; i++){
for(int j = 0 ; j < cols ; j++){
if(humans[i][j] == -1){
infectedHumans.offer(new int[] {i, j});
}else if (humans[i][j] == 1){
nonInfectedHumans ++;
}
}
}
int days = 0;
/***
* If every one is infected, then we can return 0 the current moment
*/
if(nonInfectedHumans == 0) return days;
/**
* Assuming virus can be passed in 4 directions in the cells up/down/lef/right
*/
int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
/**
* Let's traverse in the four directions
*/
while(!infectedHumans.isEmpty()){
++days;
int size = infectedHumans.size();
for(int i = 0 ; i < size ; i ++){
int [] currentPos = infectedHumans.poll();
for (int [] move : directions){
int nextMoveX = currentPos[0] + move[0];
int nextMoveY = currentPos[1] + move[1];
// if it's a valid move, not a infected human move || not an empty move
if(nextMoveX < 0 || nextMoveY < 0 || nextMoveX >= rows || nextMoveY >= cols || humans[nextMoveX][nextMoveY] == 0 || humans[nextMoveX][nextMoveY] == -1) continue;
humans[nextMoveX][nextMoveY] = -1;
infectedHumans.offer(new int[] {nextMoveX, nextMoveY});
nonInfectedHumans--;
}
}
}
return nonInfectedHumans == 0 ? (days - 1) : -1;
}
Вот и все!
