\documentclass[11pt]{article}

\usepackage{fullpage,french,epsf,fancyheadings}

\pagestyle{fancy}
\lhead{Rectangle d'aire maximale dans une grille de mots croisés}
\rhead{Jean-Christophe Filliâtre}

\newcommand\cad{c'est-\`a-dire}
\newcommand\point{{\noindent$\bullet$~}}
\reversemarginpar
\newcommand{\question}{\marginpar{\hfill$\Box$}}

\begin{document}

\begin{center}
  \LARGE\bf Rectangle d'aire maximale \\
            dans une grille de mots croisés
\end{center}
\bigskip

Etant donnée une grille de mots croisés (vide, c'est-à-dire une grille
dont certaines cases sont noires et les autres blanches), on se propose
de déterminer le rectangle d'aire maximale formé de cases blanches.
Exemple :

\bigskip
\epsfxsize=5cm%
\hfil\epsfbox{grille.eps}\hfil


\subsection*{Initialisation}

On considère une grille carrée de $N \times N$ cases et soit
$k$ le nombre de cases noires dans la grille. On représente la grille
par un tableau bidimensionnel {\tt grille} de booléens, la valeur {\tt
true} représentant une case noire. On prendra $N = 10$ et $k = 6$.

\medskip
\noindent Ecrire \question une fonction {\tt raz : unit ->~unit} qui met
toutes les cases du tableau {\tt grille} à la valeur {\tt false}
et une fonction {\tt init : unit ->~unit} qui noircit aléatoirement
{\em exactement $k$ cases} du tableau {\tt grille}. (On obtient
un entier aléatoire entre 0 et $n-1$ par {\tt random\_\_int $n$}).


\subsection*{Affichage}

On souhaite représenter graphiquement la grille et la solution du
problème. Rappel : pour utiliser la fenêtre graphique de Caml Light, on 
ouvre le module {\tt graphics} puis on appelle la fonction
{\tt open\_graph}. 

\begin{verbatim}
     #open "graphics";;
     open_graph "";;
\end{verbatim}

\noindent La taille de la fenêtre graphique est obtenue avec
{\tt size\_x()} et {\tt size\_y()}.

\medskip
\noindent Ecrire \question une fonction {\tt affiche\_case : int ->~int
->~unit} qui affiche la case $(i,j)$ de la grille (vide si le
booléen correspondant est faux, et pleine sinon). En déduire une fonction
{\tt affiche\_grille : unit ->~unit} qui affiche la grille entière.

\medskip
Un intervalle d'entiers consécutifs $i, i+1, \dots, i+d-1$, commençant
à l'entier $i$ et de longueur $d$, sera représenté par le couple 
$(i,d)$ et un rectangle de la grille par deux ses les deux intervalles
qu'il représente sur les abscisses et les ordonnées.

\begin{verbatim}
     type intervalle = Interv of int * int;;
     type rectangle  = Rect   of intervalle * intervalle;;
\end{verbatim}

\medskip
\noindent Ecrire \question une fonction {\tt affiche\_rectangle : rectangle
->~unit} qui affiche, dans une autre couleur que la grille, un rectangle
passé en argument.


\subsection*{Solution au problème}

La solution qui consiste à passer en revue tous les rectangles de la grille,
à tester s'ils sont composés de cases blanches uniquement et à conserver
celui d'aire maximale n'est pas satisfaisante car trop coûteuse.
Quelle est, d'ailleurs, la complexité de cette méthode ?

On propose ici une autre solution, plus efficace. L'idée est de remarquer
que, pour chaque case noire en position $(x,y)$ dans la grille, alors 
la solution se trouve dans l'une des quatre portions de la grille 
définies par $i<x$, $i>x$, $j<y$ ou $j>y$ (en effet, une solution
ne peut contenir la case $(x,y)$).

\medskip
Soit alors une région $\{ i,i+1,\dots,i+di-1\} \times 
\{j,j+1,\dots,j+dj-1\}$ dans laquelle on recherche une solution.
Cette solution est dont représentée par les deux intervalles
{\tt Interv ($i$,$di$)} et {\tt Interv ($j$,$dj$)}.
On commence par cherche la première colonne contenant une case noire, et 
dans cette colonne la case noire d'ordonnée la plus petite.
Soit $(i+ci,j+cj)$ cette case noire.  Exemple :

\bigskip
\epsfxsize=5cm%
\hfil\epsfbox{grille2.eps}\hfil
\bigskip

\noindent On rappelle alors récursivement la procédure sur les quatre
portions définies ci-dessus et on conserve celle d'aire maximale.
(Remarque : pour la portion de gauche, on connaît déjà le rectangle d'aire
maximale par choix de la case noire).

\medskip
\noindent Ecrire \question une fonction {\tt case\_noire : intervalle ->~%
intervalle ->~int*int} recherchant la case noire ci-dessus, donnée par
$(ci,cj)$, dans une portion de la grille définie par deux intervalles.
En déduire une fonction {\tt trouve : unit ->~rectangle} qui donne
la solution du problème. Visualiser la grille et sa solution.

\end{document}