LabASD - Torri sotto attacco

Nel gioco degli scacchi, la torre è in grado di attaccare un altro pezzo che occupi la stessa riga oppure la stessa colonna.

Questo programma legge da standard input (o da file) un intero \(n\) e una matrice di caratteri di dimensioni \(n \times n\), con \(1 \leq n \leq 100\). La matrice viene letta riga per riga. Ogni riga contiene \(n\) caratteri (più un ritorno a capo finale), ciascuno dei quali può essere . per indicare una casella vuota, oppure T per indicare che sulla casella è presente una torre.

Il programma deve stampare ATTACCO se e solo se le torri eventualmente presenti sulla scacchiera sono disposte in modo tale che ne esista almeno una coppia in grado di attaccarsi a vicenda, NO ATTACCO altrimenti. Formalmente, il programma deve stampare ATTACCO se e solo se vale almeno una delle condizioni seguenti:

1. Esiste una riga della scacchiera che contiene almeno due caratteri T;

2. Esiste una colonna della scacchiera che contiene almeno due caratteri T.

Ad esempio, data questa configurazione:

8
T.......
.T......
........
........
T.......
.....T..
....T...
.......T

il programma deve stampare ATTACCO, in quanto nella prima colonna ci sono due T.

Se la configurazione fosse:

8
T.......
.T......
........
........
........
.....T..
....T...
.......T

allora il programma deve stampare NO ATTACCO.

Viene fornito un programma torri.c e alcuni casi di test. È possibile definire ulteriori funzioni di supporto.

Per approfondire

Qual è il costo asintotico dell’algoritmo realizzato, in funzione della lunghezza \(n\) del lato della scacchiera?

File

• torri.c
• torri1.in
• torri2.in
• torri3.in
• torri4.in