Find a special connected block
All submissions for this problem are available.
Given an n*m board with a number between -1 and n*m in every entries.
And an n*m matrix M is also given, where Mi,j is the cost of selecting the (i,j) entry of the given board.
Your task is to find a connected block (which means these entries can reach each other by just go up, down, left and right without going out the block) in the board that contains at least K distinct positive numbers without any -1, and it must have minimum total cost for selecting these entries. Output the minimum total cost.
First line consists of three integers, n, m, K (1 <= n, m <= 15, 1 <= K <= 7).
The followings are two n*m matrices, the first denotes the numbers on the board and the second denotes the cost of every entry.
Namely, the first n lines contain m integers, where the jth number in ith line denotes the number on the entry (i,j) of the board. These integers are in [-1, n*m].
Next n lines contain m integers too. The jth number in ith line denotes the cost of selecting the entry (i,j) of the board. These integers are in [1, 100000].
Only one line contains the minimum cost to finish the task. If the task is impossible, output -1 please.
Input: 3 3 3 0 0 1 2 3 3 -1 2 1 3 1 5 4 10 1 9 3 4 Output: 8
|Tags||april12, hard, shangjingbo|
|Time Limit:||0.788732 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.