Knights
Турнир за Купата на Декана, 2010
Time Limit: 0.1s, Memory Limit: 64MiB
Учудващо за някои, освен страстен любител на моловете, обувките и хубавите телефони, Ели е също така голям фен на шаха. Тя до такава степен е възхитена от играта, че вече е преминала на доста по-нестандартни нейни разновидности. Например, наскоро Ели и Крис откриха играта "Рицари", която се играе на шахматна дъска с размер N на N, със стандартни шахматни коне. Играта се играе от двама души, като първият разполага произволен брой (по-голям или равен на нула и по-малък или равен на N*N) коня върху дъската, а противникът му трябва да махне минимален брой от тях, така че никои два от оставащите да не се атакуват. Можете ли да помогнете на Ели, като напишете програма, която за дадена дъска намира този минимален брой коне?
Вход
На първия ред на стандартния вход ще бъде зададено цялото число N – размерът на дъската. На следващите N реда ще има по N символа, които описват дъската. Символът '.' указва, че даденото поле е празно, а символът 'K' - че даденото поле е заето от кон.
Изход
На единствен ред на стандартния изход изведете едно цяло число – колко минимално коня трябва да бъдат премахнати от дъската, така че никои два от останалите да не се атакуват.
Ограничения
  • 1 ≤ N ≤ 50
Примерен Вход Примерен Изход
5 .K.K. K...K ..K.. K...K .K.K. 1
2 KK KK 0
8 .K.KKK.. .K..KKKK ..K....K KKKKKK.K K.K....K KK.....K ..K.K... ...K..KK 12
В първия пример конят намиращ се в средата на дъската атакува всички останали 8 коня (това са и всички начини, по които конят атакува в шаха). Ако го премахнем, останалите коне са в мирно разположение.
Мрън!