wretched's blog

By wretched, history, 13 months ago, In English

Recently,I have started to try DP problems.But for this problem(Rooks-lightoj 1005) though I have already thought much but I am not getting any idea how can i solve this problem by using DP technique.Can anyone help me what's the actual idea behind this problem!!

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Say you put rooks in $$$(r_1, c_1), (r_2, c_2), ... (r_k, c_k)$$$ positions of the board. What is the condition that no rook attacks another one?

Spoiler
  • »
    »
    13 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    if(r1==r2 || c1==c2),then (r1,c1) and (r2,c2) both of will be in attacking position?? I mean row and colomn of two positions won't be same to stay both of rooks in non-attacking position.

»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You can solve it by using DP by observing the following states.

If you are currently at the state (i, j, k) where i and j are the height and width of the chessboard respectively and k is the number of remaining rooks. Initial state would be (n, n, k).

There are two types of transitions

  1. Placing the rook on the jth row i.e. (i, j, k) to (i-1, j-1, k-1) and removing whole row as well as column from the chessboard as a valid position

2 Not placing it i.e. (i, j, k) to (i, j-1, k).

However in the first case if you are placing rook on the jth row there are total of i coulumns where you place it. Therefore dp[i][j][k] = dp[i-1][j-1][k-1]*i + dp[i][j-1][k];

I guess you can figure out base cases :)

However, it can be used simply solved by using combinatorics as already in the previous comment.