/****************************************************************************
*
* torri.c -- Torri sotto attacco
*
* Copyright (C) 2021 Moreno Marzolla
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*
****************************************************************************/
/***
% LabASD - Torri sotto attacco
% Moreno Marzolla
% Ultimo aggiornamento: 2021-07-31
![By Alan Light - Own work by the original uploader, CC BY-SA 3.0, ](ChessSet.jpg)
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](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](torri.c)
- [torri1.in](torri1.in)
- [torri2.in](torri2.in)
- [torri3.in](torri3.in)
- [torri4.in](torri4.in)
***/
#include
#include
#include
#include
#define N 100
int main( int argc, char *argv[] )
{
char s[N][N];
FILE *filein = stdin;
int i, j, n;
int r[N] = {0}, c[N] = {0};
int attacco = 0;
/* se passo due argomenti sulla riga di comando:
./torri n rho
il programma genera una scacchiera casuale di dimensione data e
con una data densità di torri. La densità rho è un valore reale
compreso tra 0 (nessuna torre) e 1 (tutte torri). */
if (argc == 3) {
const double rho = atof(argv[2]);
assert((rho >= 0.0) && (rho <= 1.0));
n = atoi(argv[1]);
assert(n <= N);
printf("%d\n", n);
for (i=0; i0 || c[j]>0) {
attacco = 1;
} else {
r[i] = c[j] = 1;
}
}
}
}
if (attacco)
printf("ATTACCO\n");
else
printf("NO ATTACCO\n");
if (filein != stdin) fclose(filein);
return EXIT_SUCCESS;
}