N-Rook

N-Queen 문제처럼 격자판 위에 여러 말을 놓되 서로 공격하지 못하게 하는 문제를 생각해 보자. 이번에는 Queen 대신 Rook을 놓는다.

Rook은 같은 행이나 같은 열에 있는 다른 말을 공격할 수 있다. 단, 두 Rook 사이에 벽이 있으면 서로 볼 수 없으므로 공격할 수 없다. 벽이 있는 칸에는 Rook을 놓을 수 없다.

구덩이가 있는 칸에도 Rook을 놓을 수 없다. 하지만 구덩이는 시야를 막지 않는다. 따라서 두 Rook 사이에 구덩이가 있더라도 같은 행 또는 같은 열에서 벽 없이 마주 보게 되면 두 Rook은 서로 공격하는 것으로 본다.

격자판의 모양이 주어졌을 때, 서로 공격하지 않도록 배치할 수 있는 Rook의 최대 개수를 구하시오.

첫째 줄에 격자의 크기를 나타내는 두 자연수 N, M이 주어진다. 격자는 N행 M열이다. (1 <= N, M <= 100)

둘째 줄부터 N개의 줄에는 격자의 모양이 한 행씩 주어진다. 각 값의 의미는 다음과 같다.

• 0: 빈 칸
• 1: 구덩이가 있는 칸
• 2: 벽이 있는 칸

첫째 줄에 배치할 수 있는 Rook의 최대 개수를 출력한다.

행과 열을 1부터 세면, 한 가능한 배치는 1행 2열과 3행 3열에 Rook을 하나씩 두는 것이다. 이때 두 Rook은 서로 공격하지 않으므로 총 2개를 놓을 수 있다.