Автор, розробник, автор розбору: Андрій Столітній
Для фіксованого стану матриці задачу можна розв'язувати за допомогою динамічного програмування. Нехай dp_{i,j} — сторона найбільшої квадратної матриці, яка складається тільки з одиниць та має правий нижній кут в . Тоді можна зробити перерахунок значень наступним чином:
А відповідь тоді буде максимумом по всіх значеннях , \displaystyle ans = \max_{1 \le i,j \le n} dp_{i,j}.
Можна помітити, що 0 \le dp_{i,j} \le n для всіх позицій . Друга важлива річ, що запити тільки можуть поміняти на , тобто відповідь ніколи не погіршується, тобто кожне зі значень dp_{i,j} ніколи не зменшується. Отже, можемо оновлювати значення частково. Якщо ми оновили значення dp_{i,j}, то воно може вплинути тільки на значення dp_{i,j+1}, dp_{i+1,j}, dp_{i+1, j+1}. Можемо перераховувати значення , і якщо воно змінилось, перерахуймо значення, які залежать від нього. Якщо вони змінились, то перерахуємо значення, які залежать від них і так далі. Це можна реалізувати або чергою, або за допомогою рекурсії. Так як кожне значення може змінюватись не більше ніж разів, а таких значень маємо n^2, то загальний час виконання програми буде \mathcal{O}(n^3).