NxN 이진 행렬에 얼마나 많은 1x2 제로 서브 매트릭스가 들어 맞습니까?

Question

1x2 (또는 2x1) 개의 제로 서브 매트릭스가 NxN 이진 매트릭스에 얼마나 잘 맞습니까? 대한

:

1 0 0 
0 0 0 
0 1 0 

결과는 3 될 것입니다. 대한

:

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

결과는 21 될 것입니다.

등등.

Answer 1

이것은 가장 효율적인 접근 방법은 아니지만이를 해결할 수있는 간단한 방법은 최대 2 부분 일치를 계산하는 것입니다 (예 : Hopfield-Karp algorithm.

키는 그리드를 체스 보드로 생각하는 것이고, 각 모양은 검은 색 사각형 하나와 흰색 사각형 하나를 연결합니다.

각 검은 색 사각형에 대해 하나의 왼쪽 노드, 각 흰색 사각형에 대해 하나의 오른쪽 노드, 검은 색 사각형 노드에서 모든 인접한 흰색 사각형 노드까지 한 개의 가장자리로 그래프를 생성하십시오.

이 그래프에서 최대 일치는 그리드에 배치 할 수있는 중복되지 않는 최대 도미노의 수에 대한 대답입니다.