Encontrar las coordenadas del triángulo rectángulo en una matriz binaria.

Digamos que tengo una matriz binaria MxN. No es necesariamente escasa. Estoy interesado en encontrar las coordenadas de los vértices de todos los triangularjs rectangularjs de la matriz. Por triángulo rectángulo, quiero decir: simule que los valores 1 o Verdadero en la matriz son vértices de triangularjs, y que los elementos 0 o Falso son nulos. Entonces, un triángulo rectángulo es un arreglo que forma visualmente un triángulo rectángulo. Por vértice me refiero al vértice que corresponde al ángulo recto del triángulo. Por ejemplo, en la siguiente matriz 5×6:

0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 

Sólo hay 1 triángulo rectángulo. Es el triángulo con vértices en: (0,2) es el vértice, (3,2) es la parte inferior izquierda, (0,4) es la parte superior derecha, donde estoy indexando desde 0, comenzando en la parte superior izquierda [Indización de Python].


Para una matriz MxN dada, quiero una función Python F (A) que devuelva una matriz L de subarrays, donde cada subarray es el par de coordenadas del vértice de los triangularjs rectangularjs en la matriz. En el caso de que el mismo elemento de la matriz sea el vértice de varios triangularjs, en última instancia solo querré subconjuntos únicos, pero por ahora la función puede duplicarlos. Como ejemplo, para la matriz A anterior, F (A) devolverá la matriz L = [[0,2]]


Mi primer pensamiento sería usar sums de filas y columnas. Vale la pena explorar esas filas con una sum de fila> = 2, y luego usar la sum de columnas> = 2. Entonces necesitarías una forma eficiente de encontrar las intersecciones. Me interesaría una función que utilice este método o cualquier otro método que pueda ser mejor y más rápido.

{Por ejemplo, como alternativa, podrías pensar en esto desde una perspectiva de la teoría de grafos. Las filas y columnas serían nodos de un gráfico bipartito [las filas serían un conjunto, las columnas del otro conjunto]. Entonces, la matriz que se muestra aquí sería un cuadrante de la matriz de adyacencia de la gráfica bipartita completa. En otras palabras, sería la parte de solo los términos cruzados entre los conjuntos de fila y columna, ya que las partes dentro del conjunto serían todas 0, ya que los nodos de fila no se conectan a otros nodos de fila; Sólo a los nodos de columna. Desde esta perspectiva, un triángulo rectángulo se vería como una trayectoria de longitud 3 en el gráfico bipartito. Creo que el enfoque matricial es más simple, pero estoy abierto a cualquier algoritmo aquí.}

Sí, creo que estás pensando demasiado en esto. Genere las sums de fila y columna, y verifique la ubicación de cada matriz para la intersección.

No he probado la syntax, pero será algo como esto:

 # Generate row and column sums row_sums = (sum(A[M]) for M in range(len(A))) col_sums = (sum([A[M, N] for M in range(len(A))] for N in range len(A[0])) # Now, check each element in the array for being a vertex vertices = [(row, col) if A[row, col] and row_sums[row] > 1 and col_sums[col] > 1 for row in range(len(A)) for col in range(len(A[0]))] # You now have a list of all solutions, with no duplicates.