Python Como obter uma determinada área de uma matriz em Python

Dark-Programação · 3 de novembro de 2019

Então, estou com um problema de programação que é basicamente esse problema ai de baixo. Ficaria muito grato se alguém pode-se me dar uma luz kk.

Preciso através da entrada do usuário retornar a soma de todas as áreas que o usuário determinou que a matriz contém, por exemplo: tenho uma matriz (determinada também pelo usuário) de 5x5 (5 linhas e 5 colunas) e ele hipoteticamente quer que eu retorne a soma de todas as 2x2 (2 linha e 2 coluna) que a matriz 5x5 contém, ou seja, ele quer todas as somas possíveis da área de tamanho 2x2 que a matriz possui. Exemplo mais palpável:

possuo essa matriz em baixo

matriz = [[1, 1, 1, 3, 1],

[1, 2, 1, 1, 1],

[1, 1, 1, 2, 1],

[1, 1, 2, 1, 1],

[1, 3, 1, 1, 3]]

O usuário quer que eu retorne todas as somas possíveis de uma área 2x2 contida na matriz 5x5, ou seja, soma = ([1, 1], [1, 2]) = 5, ([1,1], [2,1]) = 5, ([1,3], [1,1]) = 6 e assim por diante... Se não ficou muito claro peço desculpas e deixa um comentário que eu tento editar ou explicar com outras palavras. Muito obrigado!!

4 de novembro de 2019

Eu confesso que não entendi, porque uma matriz 5x5 (mesmo hipoteticamente) se o usuário exige as somas em uma a cada dois indices de uma lista que compõe a matriz toda, se voce fracionar essa matriz ela será quebrada em forma impar....{[1],[1]} {[1],[1]} [1] e vai sobrar uma coluna que não será somada com seu par ao lá por não haver.

matriz = [

[1, 1, 1, 3, 1], # 2, 4

[1, 2, 1, 1, 1], # 3, 2

[1, 1, 1, 2, 1], # 2, 3

[1, 1, 2, 1, 1], # 2, 3

[1, 3, 1, 1, 3] # 4, 2

]

Mas o que fazer com a última coluna toda em vermelho? Ela não tem com quem somar ao lado...ou quer atribuir a ela automaticamente 1 em caso vazio e somar por exemplo 1+1?

Não sei se entendi a sua questão.

Dark-Programação · 4 de novembro de 2019

55 minutos atrás, fspjonny disse:

Eu confesso que não entendi, porque uma matriz 5x5 (mesmo hipoteticamente) se o usuário exige as somas em uma a cada dois indices de uma lista que compõe a matriz toda, se voce fracionar essa matriz ela será quebrada em forma impar....{[1],[1]} {[1],[1]} [1] e vai sobrar uma coluna que não será somada com seu par ao lá por não haver.

matriz = [

[1, 1, 1, 3, 1], # 2, 4

[1, 2, 1, 1, 1], # 3, 2

[1, 1, 1, 2, 1], # 2, 3

[1, 1, 2, 1, 1], # 2, 3

[1, 3, 1, 1, 3] # 4, 2

]

Mas o que fazer com a última coluna toda em vermelho? Ela não tem com quem somar ao lado...ou quer atribuir a ela automaticamente 1 em caso vazio e somar por exemplo 1+1?

Não sei se entendi a sua questão.

Não amigo ele vai pegar o seguinte

matriz = [

[1, 1, 1, 3, 1], # Ele soma (1 +1 (linha 1) + 1 + 2 (linha 2)), depois 1 + 1 + 2 + 1, depois 1 + 3 + 1 + 1, depois 3 + 1 + 1 +1

[1, 2, 1, 1, 1], # Ele soma (1 + 2 (linha 2) + 1 + 1(linha 3)), depois 2 + 1 + 1 + 1, depois 1 + 1 + 1 + 2, depois 1 + 1 + 2 + 1

[1, 1, 1, 2, 1], # Ele soma (1 + 1 (linha 3) + 1 + 1 (linha 4)), depois 1 + 1 + 1 + 2, depois 1 + 2 + 2 + 1, depois 2 + 1 + 1 + 1

[1, 1, 2, 1, 1], # 2, 3

[1, 3, 1, 1, 3] # 4, 2

]

e assim por diante, caso ainda não ficou claro só avisar que tento explicar novamente!

Acho que dar para fazer por programação dinâmica mais não tenho mínima ideia de como faria, não encontrei na internet conteúdo que explicasse isso.

4 de novembro de 2019

Ainda não entendi!

Faça assim...esqueçe que voce está numa matriz e me mostra qual é a operação a ser realizada na lista que está abaixo e se essa mesma operação deverá ser feita e da mesma forma na demais que surgirem abaixo dela, talvez assim eu consiga entender a lógica disso tudo

[1, 2, 1, 1, 1]

Dark-Programação · 4 de novembro de 2019

2 minutos atrás, fspjonny disse:

Ainda não entendi!

Faça assim...esqueçe que voce está numa matriz e me mostra qual é a operação a ser realizada na lista que está abaixo e se essa mesma operação deverá ser feita e da mesma forma na demais que surgirem abaixo dela, talvez assim eu consiga entender a lógica disso tudo

[1, 2, 1, 1, 1]

Nessa matriz que colocou ele só poderia pegar 1xn com n<=5 se ele escolhesse um exemplo 1x2 ele iria pegar as seguintes áreas [1,2]=3, [2,1]=3, [1,1]=2, [1,1]=2, não é necessário mostrar os índices apenas os resultados possíveis. Para fixar melhor, vamos supor que temos a seguinte matriz [1, 2, 3, 4, 5] e ele quer uma área de 1x2 então devemos calcular [1,2] = 3, [2,3] = 5, [3,4] = 7 e [4,5] = 9, mesmo exemplo se sobrepõe para matrizes de NxM com área de LxC, caso ainda tiver dúvida só falar!!

brund321 · 4 de novembro de 2019

@Dark-Programação Oi Dark, tudo bem? Você ainda está à procura de uma solução? Se sim, você já tem algo pronto, já tentou fazer algo? Ou não sabe por onde começar?

Abraços!

Dark-Programação · 5 de novembro de 2019

1 hora atrás, brund321 disse:

@Dark-Programação Oi Dark, tudo bem? Você ainda está à procura de uma solução? Se sim, você já tem algo pronto, já tentou fazer algo? Ou não sabe por onde começar?

Abraços!

Oii Brund, estou sim amigo eu tentei fazer mas simplesmente deu erro, eu estou tentando resolver uma questão da obi de 2006 do nível 2, 2° fase, a colheita de caju, também tem ela no uri https://www.urionlinejudge.com.br/judge/en/problems/view/2305 , mas a ideia que eu tive fazendo umas somas que nem sei se está certo, funcionou para os 3 exemplos do uri, mas o debug já não funcionou da a resposta errada, já tentei de tudo e não conseguir e sobre essa forma que pensei da matriz eu não consigo ter uma ideia de como eu vou implementar ela, eu pensei em recursão mas não dá certo porque eu não sei qual a área que o usuário vai querer para calcular, ou seja, não sei onde iria parar a recursão, pensei em programação dinâmica mas não achei nem um conteúdo que desse uma luz sobre esse assunto, vou deixa o código que eu tentei aí em baixo caso queira dá uma olhada, muito obrigadoo!! Lembrando que não sei se está correto, acredito que está totalmente errado pois não conseguir resolver os exemplos do debug que esse exercício possui e já estou sem ideia kkk

L, C, M, N = input().split()
l = int(L)
c = int(C)
m = int(M)
n = int(N)
matriz = [0] * l
acumulado = [0] * l
max_ponto = 0
for i in range(l):
    entrada = list(map(int, input().split()))
    matriz[i] = list(entrada)
    acumulado[i] = list(entrada)
a = matriz
b = acumulado

for i in range(len(b)):
    if i<l:
        b[i][0] = 0
        for j in range(len(b[i])):
            if j < n:
                b[i][0] += a[i][j]
        for j in range(len(b[i])):
            if 0 < j < (c-n+1):
                b[i][j] = b[i][j-1] + a[i][j+n-1] - a[i][j-1]

for j in range(len(a)):
    if j < (c-n+1):
        a[0][j] = 0
        for i in range(len(a[j])):
            if i < m:
                a[0][j] += b[i][j]
        for i in range(len(a[j])):
            if 0 < i < (l-m+1):
                a[i][j] = a[i-1][j] + b[i+m-1][j] - b[i-1][j]

for i in range(len(a)):
    if i < l-m+1:
        for j in range(len(a[i])):
            if j < (c-n+1):
                if a[i][j] > max_ponto:
                    max_ponto = a[i][j]
print(max_ponto)

brund321 · 5 de novembro de 2019

@Dark-Programação Dark, eu tinha feito um algoritmo para resolver o seu problema aqui do fórum, agora que eu vi o link do uri. Já faz um tempo que não programo em python então me da um desconto rsrs. Não cheguei a testar ele com diversos inputs, apenas passei uma ideia simples para python:

def algo(matrix, a, b):
  max = 0
  
  for x in range(0, len(matrix)):
    if(x + a > len(matrix)):
      break
    for y in range(0, len(matrix[0]) - b + 1):
      sum = 0;
      for z in range(x, x + a):
        for i in range(y, y + b):
          sum = matrix[z][i] + sum
      if(sum > max):
        max = sum

  return max

Os argumentos da função são: matrix(matriz), a e b seriam equivalentes ao tamanho da área que você quer procurar por exemplo 3x2(a=3, b=2). Apenas queria contribuir com algo... Assim que eu tiver um tempinho vou tentar dar uma olhada no seu código.

Dark-Programação · 5 de novembro de 2019

33 minutos atrás, brund321 disse:
@Dark-Programação Dark, eu tinha feito um algoritmo para resolver o seu problema aqui do fórum, agora que eu vi o link do uri. Já faz um tempo que não programo em python então me da um desconto rsrs. Não cheguei a testar ele com diversos inputs, apenas passei uma ideia simples para python:
def algo(matrix, a, b):
  max = 0
  
  for x in range(0, len(matrix)):
    if(x + a > len(matrix)):
      break
    for y in range(0, len(matrix[0]) - b + 1):
      sum = 0;
      for z in range(x, x + a):
        for i in range(y, y + b):
          sum = matrix[z][i] + sum
      if(sum > max):
        max = sum

  return max
Os argumentos da função são: matrix(matriz), a e b seriam equivalentes ao tamanho da área que você quer procurar por exemplo 3x2(a=3, b=2). Apenas queria contribuir com algo... Assim que eu tiver um tempinho vou tentar dar uma olhada no seu código.

valeu amigo, muitoooo obrigado mesmo, sem estresse, eu encontrei algo sobre programação dinâmica e estou entendo mais, se conseguiu teria como me explicar a teoria que usou e se existe algum matemático que já tenha feito esse problema para eu pesquisar mais e saber como ele fez ??

brund321 · 5 de novembro de 2019

@Dark-Programação Não :(, eu tentei achar alguma coisa decente na internet, mas foi em vão rsrs. A ideia do algoritmo que eu desenvolvi é bem simples: A ideia é ir pegando cada elemento da matriz principal e ir somando os elementos que formariam uma matriz(ab) a partir desse elemento e no final desse loop da matriz(ab) que seria o loop z e i eu vejo se a soma é maior que o valor máximo já registrado e fico nesse loop até verificar todas as possíveis matrizes(ab), se você tentar utilizar esse algoritmo "na mão" você vai entender bem rapidinho como funciona, é bem simples. Eu estou com soninho não consigo explicar melhor que isso rsrs. Se você utilizar discord me adicione lá: Bruno_#5969

30 minutos depois

Achei algo interessante que me deu uma ideia, vou deixar o link do vídeo aqui:

Abraço.

Dark-Programação · 5 de novembro de 2019

9 horas atrás, brund321 disse:

@Dark-Programação Não :(, eu tentei achar alguma coisa decente na internet, mas foi em vão rsrs. A ideia do algoritmo que eu desenvolvi é bem simples: A ideia é ir pegando cada elemento da matriz principal e ir somando os elementos que formariam uma matriz(ab) a partir desse elemento e no final desse loop da matriz(ab) que seria o loop z e i eu vejo se a soma é maior que o valor máximo já registrado e fico nesse loop até verificar todas as possíveis matrizes(ab), se você tentar utilizar esse algoritmo "na mão" você vai entender bem rapidinho como funciona, é bem simples. Eu estou com soninho não consigo explicar melhor que isso rsrs. Se você utilizar discord me adicione lá: Bruno_#5969

30 minutos depois

Achei algo interessante que me deu uma ideia, vou deixar o link do vídeo aqui:

Abraço.

Muito obrigado cara, vou dar uma estudada nessa teoria, a função que você fez deu certo, mas a complexidade dele está muito alta, demorando em alguns caso de teste mais de 1 segundo kkkkk, mas deu para ter uma noção de como fazer, pena que estouro o tempo de execução kk, mas acho que consigo diminuir a complexidade da uma otimizada nele, sem estresse kk, mas então amigo, muitoooo obrigado, me ajudou muito, vou lhe adicionar no discord para a gente troca uma ideia e falar mais sobre programação, abraços e muito obrigado!!