zhouxing_algorithm05.cpp

来自「acm中的一道关于财产继承问题的源代码」· C++ 代码 · 共 80 行

#include <stdio.h>

#define MAX 20	//最大边长

///<summary>根据左上角的坐标点计算区域内的树数量</summary>
///<params name=garden>果园信息数组</params>
///<params name=x>左上角横坐标</params>
///<params name=y>左上角纵坐标</params>
///<params name=edge>卡姆兰可以拥有的土地的边长</params>
int GetTreeCount(int garden[][MAX], int x, int y, int edge)
{
	int treeCount = 0;
	for(int i = 0; i <= edge; i++)
	{
		for(int j = 0; j <= edge; j++)
		{
			treeCount += garden[x + i][y + j];
		}
	}

	return treeCount;
}

///<summary>主函数</summary>
///<remarks>
///初始化林中树(garden)为空
///输入林中胡桃树的总数和卡姆兰可以拥有的土地的边长
///输入林中树的坐标点(同时确定试探的坐标起始点(minX, minY)和终止点(maxX, maxY))
///从起始点(minX, minY)到终止点(maxX, maxY)逐个试探，计算可获得的面积内的树数量
///取最大的值输出（试探过程中如发现可获得的数量等于林中胡桃树的总数，则终止试探）
///</remarks>
void main()
{
	int max = -1;	//
	int x = 0, y = 0;	//初始试探坐标
	int edgeLength;
	int maxTreeCount;	//林中胡桃树的总数
	int treeX, treeY;
	int garden[MAX][MAX];
	int minX = MAX, minY = MAX;
	int maxX = 0, maxY = 0;

	for(int i = 0; i < MAX; i++)
	{
		for(int j = 0; j < MAX; j++)
			garden[i][j] = 0;
	}

	printf("输入林中胡桃树的总数和卡姆兰可以拥有的土地的边长:\n");
	scanf("%d %d", &maxTreeCount, &edgeLength);
	for(int r = 0; r < maxTreeCount; r++)
	{
		scanf("%d %d", &treeX, &treeY);
		garden[treeX][treeY] = 1;
		if(treeX < minX)
			minX = treeX;
		if(treeX > maxX)
			maxX = treeX;
		if(treeY < minY)
			minY = treeY;
		if(treeY > maxY)
			maxY = treeY;
	}

	for(x = minX; x <= maxX - edgeLength; x++)
	{
		for(y = minY; y <= maxY - edgeLength; y++)
		{
			int temp = GetTreeCount(garden, x, y, edgeLength);
			max = (max < temp)? temp : max;
			if(max == maxTreeCount)
				break;
		}
	}

	printf("卡姆兰最多能拥有的胡桃树数量:\n");
	printf("%d\n", max);
}