영역 색칠

면접 대비

시간 제한1초메모리 제한512 MB

요약

0, 1, 2로 적힌 격자에서 0인 칸은 칠하지 않고 그림을 정확히 복사하는 데 필요한 가로 붓질의 최소 횟수를 구합니다.

문제

산지니는 빈 모눈종이의 격자 선을 따라 주어진 그림을 똑같이 그리려고 한다. 그림은 두 가지 색으로 이루어져 있다.

붓은 가로 방향으로만 칠할 수 있으며, 붓의 두께는 1칸이다. 붓질 한 번에 칠할 수 있는 길이의 제한은 없고, 덧칠이 가능하다.

산지니가 그림을 똑같이 그리는 데 필요한 붓질의 최소 횟수를 구해보자.

첫째 줄에는 그림의 세로 길이 $N$ 과 가로 길이 $M$ 이 공백으로 구분되어 주어진다. $(2\leq N,M\leq 100)$

그다음 $N$ 줄에 걸쳐 $M$ 개의 정수가 공백으로 구분되어 주어진다. 각 정수는 그림 한 칸의 정보를 나타내며, '0'은 색이 칠해지지 않은 칸, '1'과 '2'는 각 색이 칠해진 칸을 의미한다.

그림을 똑같이 그리는 데 필요한 붓질의 최소 횟수를 출력한다.