Caramba!

All submissions for this problem are available.
BKK was playing the ever popular game, Coconut Caramba. In this game, there are N cups numbered 0 to N1 are kept upside down and one marble. Initially, the Player keeps the marble under the Xth cup. Now, S swaps are done between the cups by the Game organizer without the Playerâ€™s knowledge. In a swap, two cups are selected and swapped. The selection of two cups i and j have a probability of P[i,j] where P is the probability matrix, which is given as input. After S swaps, the Player selects the cup 'Y' and opens it. If that cup contains the marble, then the player wins. Else, he loses. As BKK is a Mathematics teacher, he wants to accurately determine the probability of winning.
Input
The first line of the input consists of t, the number of test cases. The first line of each test case contains 3 integers, N, X, Y and S denoting the number of cups, the cup under which the marble was initially placed, the cup which is checked for the marble and the number of swaps. The next N lines contain the probability matrix, with each line containing exactly N integers. Each element (i,j) denotes the probability of swapping the cup i and j my the game organizer. The matrix contains integers, which need to be transformed into probability by dividing each element with the sum of that row. Note that X and Y are zero based.
Output
The output contains a single number for each test case denoting the probability. The probability must be rounded to 4 decimal places.
CONSTRAINTS: T <=100, N <=50, 0 < X,Y < N, S <= 50
Example
Input: 1 3 0 1 2 0 1 9 1 0 1 3 7 0 Output: 0.6300
Author:  styrofox 
Tags  styrofox 
Date Added:  4032011 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 