영역 색칠

면접 대비

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

요약

0, 1, 2로 이루어진 격자가 주어질 때, 두 색의 영역을 정확히 만들기 위해 필요한 가로 붓질의 최소 횟수를 구한다.

문제

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

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

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

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

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

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