방석의 최소 개수를 BFS로 구했습니다. 

http://contest.usaco.org/TESTD... << 여기서의 TC를 확인해 보면 최소개수는 맞는데

방석을 놓는 경우의 수가 약간씩 틀리네요.

16개의 TC중 8,10,13번빼곤 다 맞는데 뭐가 문젠지 모르겠습니다.

dp로 경우의 수를 구했는데 점화식은 

"dp[N][M][K] : (N,M)위치에 K개의 방석을 놓는 개수" 형태로 했습니다.

8번TC를 예를 들면

7 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 2 0 1 1 1 0 2 0 0 0 0
0 0 3 0 0 0 1 0 1 0 0 0 4 0 0
0 0 0 0 2 0 1 1 1 0 2 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

답 : 4 , 36

저는 4, 64가 나옵니다 ㅠㅠ

dp고수님들 어떤 논리식이 잘못됬는지 도와주세요

다시보니 "방석을 최소한으로 놓았을때 목표지점까지 가는 경우의 수"로 정의하고 풀었네요 ㅋ;