11957 - Checkers
Solution Description : DP Problem find position of W (x,y) set ans[x][y]=1 and other position are 0 set ans[i][j] = ans[i+1][j+1] or ans[i+2][j+2] + ans[i+1][j-1] or ans[i+2][j-2] , Here i from x+1 to 0 and j from 0 to N If (i,j) is enemy position then do not need to calculate. Here ans[i+1][j+1] or ans[i+2][j+2] means if ans[i+1][j+1] is enemy position then need to check ans[i+2][j+2] if both ans[i+1][j+1] or ans[i+2][j+2] are enemy position then add 0 and both ans[i+1][j-1] or ans[i+2][j-2] are enemy position then add 0 finally sum all value of row 0 without enemy position and print the sum Do not forgot about mod 1000007 |
||||||||||