#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

题意整理;原题与输入输出格式对照。