John Eduard Meneses González
Tomás Santa Cruz
Manuel Juarez
Edwin Uldarico Hernandez Osorio
Daniel Ortiz
My Solution!!
Solucion en c++
#include <iostream> #include <queue> #include <vector> #include <unordered_set> using namespace std; vector<pair<int, int>> foundRottingOranges(vector<vector<int>> &grid) { vector<pair<int, int>> rottenOranges; for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[i].size(); j++) { if (grid[i][j] == 2) { rottenOranges.push_back({i, j}); } } } return rottenOranges; } int rottingOranges(vector<vector<int>> &grid) { vector<pair<int, int>> origins = foundRottingOranges(grid); if (origins.empty()) // No hay naranjas podridas { return -1; } queue<pair<int, int>> q; for (const auto &origin : origins) { q.push(origin); } unordered_set<int> visited; int days = 0; for (const auto &origin : origins) { visited.emplace(origin.first * grid[0].size() + origin.second); } while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; i++) { pair<int, int> current = q.front(); q.pop(); int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (const auto &dir : directions) { int newRow = current.first + dir[0]; int newCol = current.second + dir[1]; int newPosition = newRow * grid[0].size() + newCol; if (newRow >= 0 && newRow < grid.size() && newCol >= 0 && newCol < grid[0].size() && grid[newRow][newCol] == 1 && visited.find(newPosition) == visited.end()) { q.push({newRow, newCol}); grid[newRow][newCol] = 2; visited.insert(newPosition); } } } if (!q.empty()) { days++; } } for (const auto &row : grid) { for (int cell : row) { if (cell == 1) { return -1; } } } return days; } int main() { vector<vector<int>> grid{{2, 1, 1} ,{1, 1, 0}, {0, 1, 2}}; cout << rottingOranges(grid) << endl; return 0; }
import collections import random def bfs( apple_field: list[list[int]] ): rotten_queue = collections.deque() for i in range(len(apple_field[0])): for j in range(len(apple_field)): if apple_field[i][j] == 2: rotten_queue.append((i, j, 0)) max_time = 0 directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] while rotten_queue: x, y, time = rotten_queue.popleft() for dx, dy in directions: nx = x + dx ny = y + dy if (0 <= nx < len(apple_field)) & (0 <= ny < len(apple_field[0])): if apple_field[nx][ny] == 1: apple_field[nx][ny] = 2 new_time = time+1 max_time = max(max_time, new_time) rotten_queue.append((nx, ny, new_time)) return apple_field, max_time def generate_field(rows, cols): # Generate a random 2D array (apple field) with values 0, 1, 2 apple_field = [[random.choice([0, 1]) for _ in range(rows)] for _ in range(cols)] # Assisgns only a few rotten apples into the field for _ in range(3): x = random.randint(0, len(apple_field)-1) y = random.randint(0, len(apple_field)-1) apple_field[x][y] = 2 print("Initial apple field:") for row in apple_field: print(row) return apple_field def main(): rows, cols = 5, 5 # You can change the size as needed apple_field = generate_field(rows, cols) result_field, max_time = bfs(apple_field) print("\nApple field after propagation:") for row in apple_field: print(row) print(f"\nMax days for propagation: {max_time}") total_rotten_apples = sum( [1 if result_field[i][j] == 2 else 0 for i in range(rows) for j in range(cols)]) total_healthy_apples = sum( [1 if result_field[i][j] == 1 else 0 for i in range(rows) for j in range(cols)]) print(f"Total rotten apples: {total_rotten_apples}") print(f"Total healthy apples: {total_healthy_apples}") if __name__ == '__main__': main()
Cuantos estados posibles hay? fresca = 1 podrida = 2 vacía ? = Null ??
Si hay espacios vacíos no creo que el código sea correcto usar cultivo[x][y] != 2 pues tecnicamente infecta posiciones que ni tienen fruta ? estoy mal ?
ahora imagino que lo primero que podemos hacer es verificar si hay islas, regiones que no puedan infectar otras, y si hay mas de una saber que una infección nunca llegara al 100% del cultivo
Algo que inclui, es un catch cuando buscas en un extremo, ya que en este caso te sales del array y una bandera para que sume por una vez en la cola
from queue import Queue STEPS = [(0, 1), (0, -1), (1, 0), (-1, 0)] def rotting_oranges(farm: list[list[int]]) -> int: if farm is None or len(farm) == 0: return 0 bad_tomatoes = Queue() good_tomatoes = 0 for i in range(len(farm)): for j in range(len(farm[0])): if farm[i][j] == 2: bad_tomatoes.put((i, j)) if farm[i][j] == 1: good_tomatoes += 1 if good_tomatoes == 0: return 0 days = 1 while not bad_tomatoes.empty(): should_sum = False position = bad_tomatoes.get() for step in STEPS: next_position = (position[0] + step[0], position[1] + step[1]) try: if farm[next_position[0]][next_position[1]] == 1: should_sum = True farm[next_position[0]][next_position[1]] = 2 good_tomatoes -= 1 bad_tomatoes.put(next_position) except IndexError: continue if should_sum: days += 1 return -1 if good_tomatoes != 0 else days if __name__ == '__main__': assert rotting_oranges([[2, 1, 1], [1, 1, 0], [0, 1, 1]]) == 4 assert rotting_oranges([[1, 1, 1], [1, 1, 0], [0, 1, 1]]) == -1 assert rotting_oranges([[0, 1, 1], [1, 1, 0], [0, 1, 2]]) == 5
