Java Maior retangulo de uma matriz (logica)

[guilherme_rangel]

Olá tudo bem preciso fazer um algorítimo para determinar qual o maior retangulo de uma matriz, por exemplo:

 

digamos que seja uma matriz 5x5 e q sejam sorteadas 5 minas aletoriamente dentro da matriz o objetivo é dizer qual o maior retangulo que eu posso formar sem haver minas dentro...

 

abaixo segue uma imagem para ilustrar como estou fazendo, eu ja gerei a matriz com zeros representando o vazio _ e 1 representando as minas e segue 2 a 2 as coordenas de onde estão localizado as minas(armazenado em um vetor)

 

não vejo outra maneira de fazer a não ser encadeando inumeros for dentro de for

 

qualquer ajuda é bem vinda, qualquer ideia

 

valeu

 

retângulo é um paralelogramo formado por ângulos internos retos (90°) e congruentes (mesma medida).

 

 

[guilherme_rangel]

up

[guilherme_rangel]

up

adicionado 0 minutos depois

up

[Simon Viegas]

@guilherme_rangel, como você imaginou fazer? 

 

Em 31/08/2017 às 16:04, guilherme_rangel disse:

não vejo outra maneira de fazer a não ser encadeando inumeros for dentro de for

Tente pensar no algoritmo antes da parte técnica, ou seja, usar "um for dentro do outro" seria a técnica para "traduzir" parte do seu algoritmo para o Java... Tipo, por exemplo, o que você pode precisar é "percorrer posição por posição, coluna por coluna, linha por linha"... daí, uma "for dentro dentro do for" poderia te ajudar...
 

Então.. só para vê se eu entendi... para esse seu exemplo, a resposta seria os retângulos formados pelas coordenadas:

(0,1)(2,4) - Com área 12u
e

(0,1)(3,3) - Com área 12u
?

 

*u= unidade de medida...   (neste caso de área)

 

Eu acho que já estudei algo do tipo, mas não lembro... se é relacionado à "técnicas de buscas" ou algo assim... 

Tirando a parte "acadêmica" (que seria o caminho desejado, já que não precisamos reinventar a roda, mas apenas achar uma existente), eu imaginaria algo assim: Tentaria na "força bruta"

 

 

Obs. inicial: uma única posição pode ser considerada um retângulo, ou só partir de 2 por lado? ex.;

0 (1x1)

Daí vindo o 1x2, 2x1, 2x2, 2x3 etc
ou

0 0 (2x2)
0 0

Daí vindo o 2x3, 3x2, 3x3, 3x4.. etc...

 

 

Daí insiro 3 prerrogativas (como não sei as regras, estou supondo): [1] Os retângulos são formados a partir de 2x2. [2] Será ignorado posições repetidas, ou seja, caso seja possível formar mais de um retângulo do mesmo tamanho, o algoritmo só vai retornar 1. [3] Os retângulos tem a base perpendicular as linhas, ou seja, não pode formar retângulos inclinados.

 

VAMOS LÁ:

- A técnica se basearia em ir tentando formar retângulos menores para os maiores, verificando de posição por posição... ou seja, vai percorrendo as linhas e colunas e verificando se daria para formar retângulos... veja:

Como estipulei que o menor retângulo é de 2x2, tento achar um retângulo desse tamanho...
Agora vamos tentar achar um triângulo 2x2

Começo na primeira posição (0,0)

Posição (0,0) = 0? sim, verifica a coluna ao lado.

Posição (0,1) = 0? sim. OK. Temos um por enquanto um candidato a retângulo.
Na linha de baixo:

Posição (1,0) = 0? não, logo, da posição (0,0) não posso criar retângulos!

Vou para próxima posição (0,1)

Posição (0,1) = 0? sim, verifica a coluna ao lado.

Posição (0,2) = 0? sim. OK. Temos um por enquanto um candidato a retângulo.

Na linha de baixo:

Posição (1,1) = 0? sim, verifica a coluna ao lado.

Posição (1,2) = 0? sim, OK. Já temos um retângulo 2x2.

Daí não preciso mais procurar!

 

 

Agora vamos tentar achar um triângulo 2x3

Começo na primeira posição (0,0)

Posição (0,0) = 0? sim, verifica a coluna ao lado.

Posição (0,1) = 0? sim. OK. Temos um por enquanto um candidato a retângulo.

Posição (0,2) = 0? sim. OK. Continuamos tendo um por enquanto um candidato a retângulo.

Na linha de baixo:

Posição (1,0) = 0? não, logo, da posição (0,0) não posso criar retângulos 2x3

 

Vou para próxima posição (0,1)

Posição (0,1) = 0? sim, verifica a coluna ao lado.

Posição (0,2) = 0? sim. OK. Temos um por enquanto um candidato a retângulo.

Na linha de baixo:

Posição (1,1) = 0? sim, verifica a coluna ao lado.

Posição (1,2) = 0? sim. OK. Temos um por enquanto um candidato a retângulo.

Posição (1,3) = 0? sim. OK. Já temos um retângulo 2x3.

 

Agora iria par 2x4... por ai vai...

 

 

 

 

A mesma lógica, de força bruta, poderia ser aplicado levando em consideração uma "arresta máxima por posição". Algo como...

 

Na posição (0,0), fazendo as analises necessárias, eu conseguiria forma um retângulo linhas de até 5u, ou seja, de (0,0) té o (0,4), correto?

Ao ir na próximo linha, veria que a posição (1,0) tem mina, logo a posição (0,0) já seria descartada, pois não daria para formar nenhum retângulo nela.

 

Na posição (0,1), veria que poderia ter linhas de até 4u...indo até a coluna 4.

Ao ir na próxima linha, veria que iria também até o coluna 4 (poderia ter 2, poderia ter 3 e poderia ter 4), logo já formando um retângulo 2x4...[da inicial (0,1) a (1,4)].

 

 

 

Resumindo:

A forma que pensei seria ir tentando "construir" retângulos a partir de cada origem. Mas veja que esse método não está considerando as possibilidades repetidas... seria literalmente uma força bruta. (mas pelo menos já não continuaria quando um menor já não ser possível)

 

 

No aguardo

 

 

[guilherme_rangel]

ola Simon primeiro gostaria de agradecer o apoio, para que não haja nenhuma duvida vou colocar o enunciado do que está sendo pedido
bla bla bla bla....você só tem de receber as informações(vão vir de um txt onde tem as coordenadas das minas) sobre as posições de cada mina (coordenadas (x, y)) e determinar o maior retângulo livre de minas que pode ser encontrado, informando sua localização e sua área. Você sabe que o terreno inicial tem no máximo 100000 × 100000 unidades e que haverão no máximo 1000 minas.(no caso estou fazendo para uma matriz 5x5 com 5 minas)

 

 

no exemplo q eu postei, teria 2 resultados como segue..

 

ou seja 2 retângulos com 12 de área

 

 

 

o jeito que eu pensei inicialmente foi...
eu percorreria toda a matriz... vou tentar me expressar usando a imagem acima, eu percorreria toda a primeira linha procurando alguma mina e ja contando e armazenando os espaços em branco, qd fosse encontrada uma mina como na imagem (1,0) eu travaria a linha a partir da posição 1, e continuaria percorrendo quando achasse outra mina (3,4) eu saberia q tudo que ta acima daquela posição da coluna(e da direita ou esquerda dependendo) deveria ser decrementado das posições livres ja armazenadas dai eu saberia a area do retangulo q foi formado, e continuaria com esse fluxo até o final da matriz e iria comparando com o retangulo formado com o que está sendo formado e vendo qualq é maior pelo numero maior de area.. 

 

 

eu teria q fazer isso novemente para testar a partir da mina q foi encontrada e tentaria fazer o fluxo novamente e ...

 

 

bom eu sei que não estou nem perto e desse jeito que penssei é meio confuso...


aguardo novas sugestões. obrigado novamente!
 

[guilherme_rangel]

up

[RafaelCLP]

Questão: São dadas as posições de K minas (K <= 1000) em uma matriz M linhas x N colunas (1 <= N <= 10^5 e 1 <= M <= 10^5). Encontrar o subretângulo de maior área que não contenha nenhuma mina dentro.

 

Percorrer todo o retângulo não é uma solução eficiente, pois são M*N posições, o que chega a 10^10 (o que por si só não é sequer o suficiente - dentro dos dois for que percorrem todas as linhas x colunas, você ainda precisa de outros for pra resolver o problema). A solução está na pequena quantidade de minas.

 

Pensando com um array

Tente pensar inicialmente como seria se fosse apenas um array gigante de tamanho N com até 10^10 posições. Considere que ■ é uma posição com mina e □ uma posição sem mina. Teríamos, por exemplo:

□□■□□□□■□□□□□□□□□□■■■□□□□□□□□□□□□□...

Nesse caso, percorrer todo o array custaria 10^10, o que é demasiado. Mas se você levar em conta que o máximo temos 10^3 minas, uma solução melhor seria:

1. Criar um array A que contém a posição de cada mina (no caso acima seria: 3 8 19 20 21 ...). Para simplificar o resto do algoritmo, assuma que existe também uma mina na posição 0 e outra na posição (N+1), ficando A = 0 3 8 19 20 21 ... (N+1).

2. Ordenar o array A.

3. Para cada par de índices (i, i+1) em A, calcular o espaço vazio entre elas, ou seja, (A(i+1) - A(i) - 1); a resposta será o maior dentre esses espaços.

 

Note que esta solução tem complexidade de tempo O(|A| * log2 |A|), que é o tempo de ordenar o array das minas - aproximadamente 10^3 * log2(10^3) = 10^4 "operações". Criar e percorrer o array A demora O(|A|), sendo irrelevante perto do tempo de ordenar. É uma solução muito melhor do que percorrer as 10^10 posições do array completo.

 

Recomendo implementar o algoritmo para o problema acima antes de prosseguir. Afinal, se não conseguir resolver para um array, não adianta ainda tentar resolver o problema para uma matriz.

 

Pensando com uma matriz

Com uma matriz, fica muito mais complicado, mas a base da ideia é a mesma: calcular os retângulos vazios entre as minas.

 

Veja o exemplo a seguir, em que temos um mina em (x, y) = (4, 2), e outras em (14, 1) e (14, 3).

□□□□□□□□□□□□□■□□□□□□

□□□■□□□□□□□□□□□□□□□□

□□□□□□□□□□□□□■□□□□□□

□□□□□□□□□□□□□□□□□□□□

Pense o seguinte: se eu estou na coluna 4, e a próxima mina à minha direita está na coluna 14, para quê eu vou verificar as colunas 5, 6, 7, ...? Não vai ter nada até chegarmos na coluna 14, então eu posso pular pelo menos direto pra coluna 13 e expandir minha área até aí. Nenhuma dessas colunas afetará a altura do retângulo. Na coluna 14 eu posso ter que recalcular a altura, mas até lá, nada precisa ser feito.

 

A partir daqui existem várias soluções possíveis. Não sei exatamente qual seria a mais fácil pra você entender, então escolhi a mais fácil de eu explicar.

 

Simplificando o problema: Xa fixo

Vamos simplificar um pouco o problema. Eu quero que você me dê o maior subretângulo cuja coluna da esquerda seja Xa. Ou seja, eu quero que você ache o trio (Ya, Xb, Yb) tal que o retângulo de (Xa, Ya) até (Xb, Yb) seja o de maior área possível dentre todos os que começam em Xa (Xa <= Xb e Ya <= Yb). Note que a diferença é que no problema inicial eu quero que você ache o (Xa, Ya, Xb, Yb) que maximize a área, e neste simplificado eu te dou um Xa fixo.

 

Afirmamos que um retângulo que começa na coordenada (Xa, Ya) e termina na coordenada (Xb, Yb) inclui todos os pontos (x, y) tal que Xa <= x < Xb e Ya <= y < Yb. Logo, sua área é |Xb-Xa| * |Yb-Ya|.

 

Para resolver o problema, vamos começar com um único segmento vertical (1, M+1), que indica que temos um retângulo que começa na coordenada (Xa, 1) e termina na coordenada (Xb, M+1), onde Xb = Xa inicialmente.

 

O que queremos agora é tentar expandir o Xb para aumentar a área desse retângulo. Se você prestou atenção até agora, já percebeu que não precisamos aumentar o Xb de 1 em 1. Basta pular direto para a primeira mina que esteja à direita do Xb atual (e isso pode ser feita com um array ordenado das posições das minas). Veja o exemplo abaixo com Xa = 3 e M = 5:

□□□□□□□□□□□□□

■□□□□□■□□□□□□

□□□□□□□□□□□□□

□□□□□□□□□■□□□

■□□□□□□□□□□□□

Começamos com o segmento (1, M+1) = (1, 6). Em vez de tentar expandir o Xb de 1 em 1, podemos pular direto pra Xb = 7, pois não existe nenhuma mina entre o 3 e o 7.

 

Agora, que encontramos nossa primeira mina em (7, 2), vamos calcular a área do retângulo (Xa, 1) até (Xb, 6) = (3, 1) até (7, 6), que dá |7-3||6-1| = 4*5 = 20 (área em verde na "figura" acima). Por enquanto, essa é nossa maior área. Como temos uma mina em (7, 2), vamos quebrar agora nosso segmento vertical (1, 6) em dois: (1, 2) e (3, 6), conforme a "figura" a seguir:

□□□□□□□□□□□□□

■□□□□□■□□□□□□

□□□□□□□□□□□□□

□□□□□□□□□■□□□

■□□□□□□□□□□□□

Avançamos o Xb para 10, que é onde está a próxima mina. Note que essa mina vai quebrar o segmento (3, 6) em dois, então calculamos a área desse segmento: |6-3||10-3| = 21. É maior que a nossa antiga área de 20, então guardamos essa como maior área. Agora, quebramos o segmento (3, 6) em (3, 4) e (5, 6). Note que não precisamos calcular a área do retângulo formado pelo segmento (1, 2) ainda porque ela só tem a aumentar (até que achemos uma mina que a quebre em dois segmentos ou acabe o retângulo).

□□□□□□□□□□□□□

■□□□□□■□□□□□□

□□□□□□□□□□□□□

□□□□□□□□□■□□□

■□□□□□□□□□□□□

Não há mais minas, então chegamos ao fim do retângulo e temos 3 segmentos. Calculamos a área dos retângulos formados por cada um desses segmentos, que coincidentemente dá 11 pra todos, e comparamos com a maior que temos até agora, 21. A maior área, portanto, é 21.

 

Vamos agora ao algoritmo.

 

Detalhe de implementação: é importante você notar que se temos um segmento (i, j) e encontramos uma mina em um certo y (i <= y < j), quebramos esse segmento nos segmentos (i, y) e (y+1, j). Inicialmente temos (1, M+1), e se encontramos 3 minas, y1, y2 e y3 (y1 < y2 < y3), acabamos com os segmentos (1, y1), (y1+1, y2), (y2+1, y3), (y3+1, M+1). Logo, sabendo os y das minas, nós sabemos também os segmentos. A vantagem disso é que podemos representar os segmentos como um conjunto ordenado dos y encontrados. Esse conjunto, em vez de guardar (1, y1), (y1+1, y2), (y2+1, y3), (y3+1, M+1), pode simplesmente guardar os inteiros 0, y1, y2, y3, M+1. Assim basta pegar dois inteiros consecutivos i e j nesse conjunto para sabermos que temos o segmento (i+1, j).

 

Segue o algorítmo:

1. Monte o array A de pares <x, y> com as posições das minas. Ordene esse array (da esquerda pra direita).

2. Crie um TreeSet S de inteiros que vai guardar os segmentos. Adicione inicialmente os inteiros 0 e M+1 nesse Set, indicando que há apenas o segmento (1, M+1).

3. Encontre a primeira mina (Xb, y) em A tal que Xb > Xa.

(Loop):

4. Pegue Er = S.tailSet(y+1) (o primeiro elemento Er de S tal que Er >= y+1), e pegue o elemento El imediatamente anterior a Er. Temos, portanto, o segmento (El+1, Er). Ele forma o retângulo (Xa, El+1) até (Xb, Er), com área |Xb-Xa||Er-(El+1)|.

5. Se essa área for maior do que a maior encontrada até agora, atualize a maior área.

6. Adicione y ao set S.

7. Se houver minas restantes, avance para a próxima mina e atribua a (Xb, y) a coordenada dessa mina, e volte ao passo 4. Senão, continue para o passo 8.

:(Fim do loop)

8. Para cada par (i, j) de elementos consecutivos em S, compare a área |N-Xa|*|j-i| com a maior área encontrada até então, mantendo a maior entre as duas.

 

Complexidade: o algoritmo precisa percorrer as K minas, e pra cada mina (x, y) precisa acessar o conjunto S pra pegar o tailSet(y+1), e depois pra inserir y em S. Tanto tailSet quanto inserção tem complexidade O(log2 X), onde X é o número de elementos no Set. No máximo inserimos um elemento por mina nesse Set, portanto X é no máximo K. A complexidade final do algoritmo é O(K * log2 K).

 

Expandindo a solução: determinando os Xa importantes

Agora que temos uma solução que pode ser aplicada a um Xa fixo, basta sabermos quais são os Xa importantes. Como repetido várias vezes até agora, o maior retângulo sempre está encostado (por todos os 4 lados) em minas e/ou nas bordas do retângulo completo (afinal, se não está encostado nem na borda nem em uma mina na esquerda, por exemplo, podemos aumentar a área pra esquerda até bater em algo). Logo, pra cada mina (x, y), basta usar Xa = x+1. Não esquecer também de considerar Xa = 1 (encostado na borda esquerda).

 

Complexidade: como são K minas, e pra cada Xa a complexidade é O(K * log2 K), a complexidade final é O(K² * log2 K). Isso dá cerca de 10^3 * 10^3 * log2 (10^3) = 10^7 operações.

 

 

 

Espero que tenha entendido. Deve estar bastante confuso, mas pra mim já foi bastante complicado explicar isso e esse foi o único algoritmo dentre os que pensei que consegui achar alguma forma de explicar sem ter que fazer um vídeo.

 

Dúvidas pergunte.