12961번 - 체스판 2

동혁이는 직사각형 체스판을 가지고 있다. 체스판의 행과 열은 0번부터 시작한다. i행 j열의 색은 i+j가 짝수이면 검정색, 홀수이면 흰색이다. 체스판의 일부 칸에는 말이 놓여져 있다.

윤호는 L-모양으로 생긴 타일을 매우 많이 가지고 있다. 타일은 체스판의 한 칸 크기와 같은 정사각형을 아래 그림처럼 3개를 이어 붙인 형태이다.

OO
O

윤호는 동혁이의 체스판에 다음 조건을 만족시키면서 타일을 체스판 위에 올려 놓으려고 한다.

• 모든 타일은 회전 시킬 수 있다. (90, 180, 270도)
• 모든 타일은 체스판 위의 세 칸을 덮어야 한다.
• 타일은 겹치면 안 된다.
• 말이 이미 올려져있는 칸은 타일이 덮을 수 없다.
• 타일의 꼭짓점 칸(두 정사각형과 붙어있는 칸)은 체스판의 검정 칸을 덮어야 한다.

윤호가 놓을 수 있는 타일의 최대 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 체스판의 행의 크기 R과 열의 크기 C가 주어진다. (1 ≤ R ≤ 47, 1 ≤ C ≤ 47)

둘째 줄부터 R개의 줄에 체스판의 상태가 주어진다. 'X'는 말이 놓여져 있는 상태, '.'는 빈 칸이다.

윤호가 놓을 수 있는 타일의 최대 개수를 출력한다.