在N×MNtimes MN×M 的矩阵中，每个格子有一个权值，要求寻找一个包含 K 个格子的凸连通块（连通块中间没有空缺，并且轮廓是凸的，如书中图片所示），使这个连通块中的格子的权值和最大，求出这个最大的权值和，并给出连通块的具体方案，本题有SPJ，输出任意一种方案即可，N,M≤15,K≤225N,M leq 15,K leq 225N,M≤15,K≤225， According to top-s
在N×MNtimes MN×M 的矩阵中，每个格子有一个权值，要求寻找一个包含 K 个格子的凸连通块（连通块中间没有空缺，并且轮廓是凸的，如书中图片所示），使这个连通块中的格子的权值和最大。求出这个最大的权值和，并给出连通块的具体方案。本题有SPJ，输出任意一种方案即可。N,M≤15,K≤225N,M leq 15,K leq 225N,M≤15,K≤225。 According to top-secret A-country plans, I-country is divided into N×MN times MN×Mequal squares, each square contains some oil resources. They want to occupy all the territory of I-country, but the UN (United Nations) will allow them to occupy only K squares. Of course, A-country want to get control over as many oil as possible, but, they will have to guard all their territory. So, they need their territory to be easy-controlled, i.e. from any square to any it must be possible to get moving only along two directions (selected from the next list: left, right, up, down; for different squares pairs of directions may differ). You are to write a program, which determinies, what squares will be occupyed by A-country. If there are several solutions, you may output any.
