Optimized Infection Simulation on a 2D Grid

Problem: Optimized Infection Simulation on a 2D Grid Given an n x m grid, 1 means infected and 0 means uninfected. Every minute, an uninfected cell becomes infected in the next minute if at least K of its four orthogonal neighbors have been infected cumulatively. Simulate until no new infections occur. Output the number of minutes until stabilization and the final grid. Avoid scanning the full grid every minute; design an implementation better than naive per-round O(nm) scanning. Input First line: n m K Next n lines: binary strings of length m. Output First line: minutes until stabilization. Next n lines: final grid. Constraints 1 <= n, m <= 1000 0 <= K <= 4 the initial grid may be all 0 or all 1 Example Input 3 3 1 100 000 000 Output 4 111 111 111