Color them all
All submissions for this problem are available.
You are given a square board of size n*n. A principal diagonal of a matrix is the diagonal connecting points (1,1) and (n,n). All the diagonals parallel to this diagonal (including itself) are called "Colorful diagonals". The given board has n*n small square boxes. Now you want to paint the board with some color. Some of the boxes are damaged beyond repair and you dont need to paint them.
- You have to start with one of the end diagonals. (i.e. diagonal joining (1,n) and (1,n) (upper side) or the diagonal joining (n,1) and (n,1) (lower side).
- You can not paint a diagonal unless one of its neighbour diagonals is painted.
- Every time the cost to paint a diagonal is (number of colorable boxes in the diagonal)*costA .
- Now at any point of time you can change the side of the matrix you are painting. But whenever you change the side cost for that diagonal becomes (number of colorable boxes in the diagonal)*costB.
- Remember that the cost becomes costB only for one diagonal after the change of the side.
- Now your task is to paint the matrix in minimum cost.
First line will contain n (size of the square board), costA, costB. (Read the problem statement to know what is costA and costB).
Next n lines will contain n integers each representing the status of the box at (i , j) position. 1 represents the box to be colored and 0 represents the damaged box.
Output a single line denoting the minimum cost to paint the matrix.
- 1 ≤ n ≤ 500
- 1 ≤ costA , costB ≤ 2*106
Input: 5 2 6 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 Output: 34
|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, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.