검은 칸과 하얀 칸으로 이뤄진 N행 N열의 격자가 있다.

검은 사각형이란 격자의 칸들을 사각형의 형태로 선택했을 때, 포함되는 칸들의 색이 모두 검은색이고, 선택한 칸의 수가 2개 이상인 것을 말한다.

위의 왼쪽 그림에서 1번의 경우에는 선택한 칸의 색이 모두 검은색이 아니기 때문에 검은 사각형이 아니다. 2번의 경우에는 선택한 칸의 색은 모두 검은색이지만 선택한 칸의 개수가 1개이기 때문에 검은 사각형이 아니다.

격자가 주어졌을 때, 선택한 칸이 서로 겹치지 않게 한번에 2개의 검은 사각형을 만들 수 있는 모든 경우의 수를 출력하는 프로그램을 작성하라.

검은 사각형 timer 1s memory 128MB

검은 사각형 1s 128MB