Submatriz dentro de una Matriz (Pedregal - OIA)

[mellomda]

Hola gente, bueno, no sabia donde poner este tema asi que lo puse aca. Si estoy equivocado, por favor diganme.
El problema que tengo y por el cual les pido ayuda, es que no termino de saber como hacer para buscar dentro de una matriz si hay lugar para otra matriz mas pequeña. El problema es de la OIA (Olimpiadas Informaticas) y se titula "Construyendo Una Casa En Un Pedregal"... Paso a explicar (sencillamente) el problema que tengo:

1- Tengo una matriz de 5x5 (por ejemplo) llena de ceros. esta matriz seria el terreno o como quiera llamarse
2- Dentro de este terreno tengo peldaños, que los marco con un numero 1 para identificar la posicion ocupada por un peldaño
3- Por ultimo tengo una matriz mas pequeña que la primera de 3x2 (por ejemplo) (esta seria la casa a ubicar en el terreno)

lo que yo tengo que averiguar es si la matriz de 3x2 (la casa) entra en algun lugar de la matriz de 10x10 (el terreno) teniendo en cuenta los peldaños (posiciones ocupadas por un numero 1). Ejemplo:

Matriz de 5x5 (Con Peldaños)
-1-0-0-0-1-
-1-0-0-0-1-
-1-0-0-1-1-
-0-0-1-0-0-
-0-0-1-0-1-

Matriz de 3x2
1-1-1
1-1-1

Como se puede ver, la matriz de 3x2 cabe en la de 5x5, y la posicion superior izquierda donde entraria, seria la posicion "2;1" de la matriz de 5x5 (sin tener en cuenta que los vectores comienzan de la posicion cero).

Hay muchas cosas a tener en cuenta, como la direccion de la salida de la casa (Norte-Sur-Este-Oeste), la posibilidad de que alla mas de un lugar para ubicar la casa, etc. Pero lo que yo necesito es aunque sea una idea de como buscar una posible ubicacion de la casa dentro del terreno... Desde ya muchas gracias, y espero alguna respuesta.

PD: Para los que quieran ver el problema completo tal cual esta en la pagina de la OIA, entren al google, pongan "OIA programacion", apreten el primer link, luego apreten donde dice "Problemas" (esta coloreado en verde) y ahi tienen una lista interminable de problemas de programacion... este en particular se encuentra con el nombre de "Construyendo una Casa En Un Pedregal" (Año 2007, Nivel 2). No pongo el link por que el foro no me deja (Aún no tienes permitido poner enlaces ni imágenes).

[[duilioisola]]

Supongo que la forma más simple es recorrer la matriz "Terreno" buscando espacio suficiente.
Si la matriz "casa" es de 3x2, buscarás desde la primera posicion hasta la longitud del terreno - 3.
for i := 0 to Terreno.Largo - Casa.Largo

Cuando encuentras un lugar sin "peldaño" buscas los 3 siguientes para ver si están vacíos para construir la casa
for j := i to i + Casa.Largo

Si las tres posiciones están limplias, haces lo mismo para las posiciones que ocuparía la casa en las siguientes líneas
for k := l to Casa.Alto
for m := i to i + Casa.Largo

Todo esto sería mejor hacerlo con while para que ni bien encuentres una celda ocupada salgas de la búsqueda y sigas con la siguiente celda.

Si también tienes que buscar la casa en otra orientación, deberías ver primero que no sea simetrica después de girarla (un cuadrado por ejemplo) y repetir la búsqueda

[[duilioisola]]

No lo probé porque no tengo Delphi a mano, pero supongo que es aproximandamente lo que quieres:
Recorre de arriba a abajo y de izquierda a derecha el terreno.
Si encuentra una celda vacía recorre de arriba a abajo y de izquierda a derecha las posiciones que ocuparía la casa.
Si durante la búsqueda encuentra una celda ocupada, avanza la posición, porque estoy seguro de que no entrará.

Código Delphi [-]
const
  LargoTerreno=10;
  AltoTerreno=10;
  LargoCasa=3;
  AltoCasa=2;
var
  Terreno : array[1..LargoTerreno, 1..AltoTerreno] of byte;
  Casa : array[1..LargoCasa, 1..AltoCasa] of byte;
  tx, ty : byte;
  cx, cy : byte;
  CeldaOcupada : boolean;
begin
  // Recorro el terreno con dos whiles;
  // Solo recorro hasta la posicion donde la casa es mas grande que el terreno
  tx := 1;
  ty := 1; 
  while (tx < LargoTerreno) and (LargoTerreno - tx > LargoCasa) do
  begin
    while (ty < AltoTerreno) and (AltoTerreno - ty > AltoCasa) do
    begin
      // Si no está ocupada
      if (Terreno[tx, ty]=0) then
      begin
        // Recorro el terreno que ocuparía la casa buscando espacio
        // Aqui estoy seguro de que la casa entra dentro del terreno
        cx := 1;
        cy := 1; 
        CeldaOcupada := False;
        while (cx < LargoCasa) and (not CeldaOcupada) do
        begin
          while (cy < AltoCasa) and (not CeldaOcupada) do
          begin
            if (Terreno[tx+cx-1, ty+cy-1]=1) then
            begin
              CeldaOcupada := True;
              // Avanzo la posición de búsqueda.
              ty := ty + cy;
            end;
            inc(cy);
          end;
          inc(cx);
          cy := 1;
        end;
        // Si ninguna de las celdas esta ocupada encontré un lugar
        if (not CeldaOcupada) then
          ShowMessage(Format('Lugar encontrado: (%d;%d)', [tx, ty]));
      end;
      inc(ty);
    end;
    inc(tx);
    ty := 1;
  end
end;

[mellomda]

muchisimas gracias duilioisola, mientras esperaba una respuesta me puse a hacerlo y efectivamente lo hice practicamente IGUAL a lo que me decis, pero estaba MAL, jaja, yo lo que hacia era recorrer todo el terreno y verificar si no habia posiciones ocupadas:
1- Si habia: Seguia recorriendo
2- Si no habia: "Recorria solo de izquierda a derecha para verificar que la casa entre (sin que hubiese una posicion ocupada)"

Efectivamente funcionaba (eso me parecia), pero claro, solo con matrices cuadras, ya que era lo mismo recorrer de una u otra forma, pero cuando la matriz no era cuadrada y la casa podia entrar en forma vertical, entonces no andaba. Viendo tu ejercicio, me aclaro la idea a la perfeccion... Le hice algunas modificaciones (sobre todo para adaptarlo a C++), y me anda de lujo

Muchisimas gracias duilioisola, te agradezco por tu tiempo, y no solo era lo que pedia sino mas todavia...