Атакуючі тури

Красиві шахові задачі є поширеним джерелом вправ з алгоритмів. Починаючи з відомої задачі про $8$ ферзів, було зроблено кілька узагальнень і варіацій. Одна з них - завдання про $n$ тур, що складається у розміщенні $n$ тур на шахівниці розміром n \times n так, щоб вони не били одна одну.

Професор Ананд презентував завдання про $n$ тур студентам. Оскільки тури б'ють одна одну лише тоді, коли стоять на одній горизонталі чи вертикалі, студенти швидко знайшли розв'язок, розмістивши тури на головній діагоналі. Професор вирішив ускладнити задачу, додавши декілька пішаків: дві тури б'ють одна одну лише тоді, коли знаходяться на одній горизонталі чи вертикалі, і при цьому між ними немає пішаків. Крім того, пішаки займають деякі клітини, що обмежує розташування тур.

За заданим розміром дошки та розміщенням пішаків визначте максимальну кількість тур, які можна розставити на порожніх клітинах так, щоб жодні дві з них не били одна одну.