#185. I-country
I-country
题目描述
在 N×M 的非负权矩阵中选择 K 个格子,使权值和最大。所选区域须四连通,且任一行、任一列中被选择的格子都连续。K=0 时选择空区域。
输入格式
首行 N、M、K,1≤N,M≤15,0≤K≤NM;随后 N 行,每行 M 个 0 到 1000 的权值。
输出格式
首行输出 Oil : X,X 为最大权值和;再输出 K 行行号、列号(均从1开始),给出最优方案。多解可输出任意一种。
样例输入
2 3 4
10 20 30
40 2 3
样例输出
Oil : 100
1 1
1 2
1 3
2 1
题意整理;原题与输入输出格式对照。