[C] Help Caretaker

왼쪽 위에서부터 차례대로 놓아가는 백트래킹으로 풀 수 있다. 다음과 같은 가지치기 하나만으로도 시간 내에 답을 구할 수 있다. 현재 (i, j) 를 살펴봐야 하는 때라면 남은 칸의 수는 대략 (n*m - (i*m+j)) 칸 일 것이다. 현재까지 놓은 T의 개수를 cnt, 현재 구한 제일 좋은 답을 ans 라고 하면 cnt + (n*m - (i*m+j))/6 <= ans 라면 여기서 더 뻗어나가도 답을 갱신할 가능성이 없으므로 여기서 가지를 치면 된다. 직전 2줄의 상태를 관리하는 bitmask DP 로도 해결할 수 있다.