Elabore um algoritmo que, dada uma matriz NxM, encontre todos os seus “pontos cela”. Denomina-se ponto cela, todo elemento da matriz que seja o maior elemento de sua linha e, também, o maior elemento de sua coluna.

Passo 1

Estamos com uma matriz de tamanho N×M e queremos encontrar todos os pontos cela, ou seja, entradas que sejam ao mesmo tempo o maior valor de sua linha e o maior valor de sua coluna.
A ideia central é usar dois vetores auxiliares: um para guardar, para cada linha i, o valor máximo daquela linha; e outro para guardar, para cada coluna j, o valor máximo daquela coluna.

Passo 2

Primeiro, percorremos todas as linhas. Para cada linha i, varremos as colunas j de 1 a M e achamos o maior valor. Armazenamos esse valor em rowMaxVal[i].
Em seguida, percorremos todas as colunas. Para cada coluna j, varremos as linhas i de 1 a N e achamos o maior valor. Armazenamos esse valor em colMaxVal[j].

Passo 3

Por fim, fazemos um último duplo laço em toda a matriz. Para cada posição (i,j), se A[i][j] for igual a rowMaxVal[i] e também igual a colMaxVal[j], então (i,j) é um ponto cela e a gente o registra.

Passo 4

O custo final desse método é O(N·M), pois cada uma das três passagens (linhas, colunas e verificação) percorre a matriz no máximo uma vez. Além disso usamos espaço auxiliar O(N+M).

Resposta

Algoritmo EncontrarPontosCela(A, N, M):
// A é a matriz N×M
criar vetor rowMaxVal[1…N]
criar vetor colMaxVal[1…M]
// Computa máximo de cada linha
para i de 1 até N:
rowMaxVal[i] = A[i][1]
para j de 2 até M:
se A[i][j] > rowMaxVal[i] então
rowMaxVal[i] = A[i][j]
// Computa máximo de cada coluna
para j de 1 até M:
colMaxVal[j] = A[1][j]
para i de 2 até N:
se A[i][j] > colMaxVal[j] então
colMaxVal[j] = A[i][j]
criar lista resultado vazia
// Identifica pontos cela
para i de 1 até N:
para j de 1 até M:
se A[i][j] == rowMaxVal[i] e A[i][j] == colMaxVal[j] então
adicionar (i, j) em resultado
retornar resultado

Exercícios relacionados