Microsoft DreamSpark Yatra Publicity
All submissions for this problem are available.
The success of an event depends deeply on the positive publicity it gets in other colleges. Some factors lead to positive publicity while others lead to the negative.Also many colleges are so tied up socially that a publicity in one spreads the news to others so it cannnot be publicized after a partner college is publicized.
Now, consider the fact that different colleges across India are carrying out Microsoft DreamSpark Yatra 2011 in their respective campus auditoriums or townhalls.
You have been provided with the publicity values of all the colleges as a matrix of MxN. The host college for DreamSpark Yatra to be at x,y. Each visit to publicity must be 4-connected to the current college, and the City block distance from the host college should increase by 1 at each step.
A City block distance is given by (|x-xi|+|y-yi|).
A 4-connected college in a matrix is directly adjacent to the college either up, down left or right.
Your task is to find the maximum publicity that a DreamSpark Yatra team can get given the host college location and the publicity matrix.
Problem Setter: Shahzor Khan
First line of Input gives T (1 < T < 1000), the number of test cases followed
by T Test Cases.
First line of each test case contains 4 numbers N,M(1<=N,M<=20) ,x(1<=x<=N),y
(1<=y<=M) as in statement seperated by a single space.
The next N lines have M integers each describing the Publicity matrix. The first
integer represents the publicity value at position (1,1).
For each test case print the maximum possible value of Publicity that can be
Input: 2 4 4 2 2 1 5 2 7 3 5 6 7 9 -5 3 1 7 8 0 0 2 2 1 1 5 8 9 1 Output: 25 15
|Time Limit:||0.142857 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, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.