USACO 2011 November Silver - Cow Beauty Pageant (Silver Level)

'X'로 표시되어 있는 세 영역을 하나의 영역으로 합치기 위해서 'X'를 추가적으로 칠해야 하는 최소값을 구하는 문제이다.

세 영역밖에 없으므로, 연결하는 경우의 수는 두 가지밖에 없다. 영역을 두개씩 각각 연결하거나(예제), 세 영역의 중간지점에서 세 영역을 동시에 연결하는 경우가 있다. 격자가 최대 50*50=2500개밖에 없으므로, 모든 점들 사이의 경우를 다 따져봐도 2500^2=625만가지이다. 따라서 단순하게 모든 경우를 따져도 시간 안에 답을 구할 수 있다.