```// breche.c

// << Algorithmique du texte >>
// Maxime Crochemore, Christophe Hancart et Thierry Lecroq
// Vuibert, 2001.

#include <stdio.h>
#include "chl.h"

#define D(i,j)   td[((i) + 1)*(n + 1) + (j) +1]
#define I(i,j)   ti[((i) + 1)*(n + 1) + (j) +1]
#define T(i,j)   t[((i) + 1)*(n + 1) + (j) +1]
#define Sub(a,b) (a == b ? 0 : 3)
#define INFINI   ((unsigned int)(~0)>>3)

int breche(Mot x, Longueur m, Mot y, Longueur n, int g, int h) {
int i, j, *t, *td, *ti;

td = (int *)malloc((m + 2)*(n + 2)*sizeof(int));
if (td == NULL) error("breche");
ti = (int *)malloc((m + 2)*(n + 2)*sizeof(int));
if (ti == NULL) error("breche");
t = (int *)malloc((m + 2)*(n + 2)*sizeof(int));
if (t == NULL) error("breche");

for (i = -1; i <= m + 1; ++i)
D(i, -1) = I(i, -1) = INFINI;
T(-1, -1) = 0;
T(0, -1) = g;
for (i = 1; i <= m - 1; ++i)
T(i, -1) = T(i - 1, -1) + h;
T(-1, 0) = g;
for (j = 1; j <= n - 1; ++j)
T(-1, j) = T(-1, j - 1) + h;
for (j = 0; j <= n - 1; ++j) {
D(-1, j) = I(-1, j) = INFINI;
for (i = 0; i <= m - 1; ++i) {
D(i, j) = MIN(D(i - 1, j) + h, T(i - 1, j) + g);
I(i, j) = MIN(I(i, j - 1) + h, T(i, j - 1) + g);
T(i, j) = MIN(T(i - 1, j - 1) + Sub(x[i], y[j]),
MIN(D(i, j), I(i, j)));
}
}
return(T(m - 1, n - 1));
}
```