Bonjour,

Les Golgoths ne tolèrent pas les tricheurs, et ont donc mis au point une technique qui ne permet à aucun élève d’une classe de tricher lors d’un examen important.

Comme le montre l’image ci dessus, l’élève peux essayer de tricher en regardant sur la copie en haut à droite, en haut à gauche, à droite et à gauche. Les Golgoths ont donc décidé qu’il serait interdit de placer les élèves de sorte qu’ils puissent effectivement tricher. Il y a aussi dans les salles de classe des places qui ne sont plus praticables, où les chaises ou les tables sont cassées, ou absentes.

Votre tâche est donc de déterminer, suivant la classe que nous vous donnerons, le maximum d’élèves que la classe peut contenir, sans qu’aucun des élèves puisse tricher.

La première ligne du fichier vous donne le nombre de salles de classe.
Chaque salle de classe est décrite comme ceci : deux entiers, la longueur et la largeur de la salle.
Les lignes suivantes décrivent la classe en elle même. Chaque caractère est soit un ‘.’ ce qui signifie que la place peut être occupée, soit un ‘x’ qui signifie que la place ne peut pas être occupée (la table est cassée…)

Pour chaque classe, vous devez indiquer le maximum d’élèves que la classe peut contenir sans qu’aucun des élèves puisse tricher.

voici le fichier des classes

Ce problème est inspiré d’une épreuve de Google code Jam (GCJ 2008 Round 3).