Я окрім перебору нічого придумати не можу.
Я не тру програміст.

При тих обмеженнях цілком можна обійтись і перебором: всього Σn² = 385 перевірок в найгіршому випадку - 1 для квадрата 10х10, 4 для квадратів 9х9 і т. д.

Можна піти знизу і почати з пошуку квадратів 2х2 з найменшою кількістю одиниць. Якщо в такому квадраті одиниць менше ніж К, то з кожного такого квадрата і клітинок, які його оточують, утворити квадрати 3х3, далі взяти до уваги лише ті, в яких одиниць найменше, повторити (для 4х4, 5х5 і до просвітлення). Такий алгоритм буде досить швидко знаходити шукане число, але от чомусь я не впевнений, що не може бути екзотичного випадку, коли найбільший квадрат будується не на основі квадрата з найменшою кількістю одиниць з попереднього кроку.