洛谷P1086 花生采摘

洛谷刷題記錄——P1086 花生采摘

又是一道水題，不過對于自己的能力還蠻考驗的，畢竟自己太菜了/(ㄒoㄒ)/~~

好希望以後發的部落格都是些高難度的算法題。當下還是一步一個腳印地前進吧

題目描述

魯賓遜先生有一隻寵物猴，名叫多多。這天，他們兩個正沿着鄉間小路散步，突然發現路邊的告示牌上貼着一張小小的紙條：“歡迎免費品嘗我種的花生！――熊字”。

魯賓遜先生和多多都很開心，因為花生正是他們的最愛。在告示牌背後，路邊真的有一塊花生田，花生植株整齊地排列成矩形網格（如圖11）。有經驗的多多一眼就能看出，每棵花生植株下的花生有多少。為了訓練多多的算術，魯賓遜先生說：“你先找出花生最多的植株，去采摘它的花生；然後再找出剩下的植株裡花生最多的，去采摘它的花生；依此類推，不過你一定要在我限定的時間内回到路邊。”

我們假定多多在每個機關時間内，可以做下列四件事情中的一件：

1、從路邊跳到最靠近路邊（即第一行）的某棵花生植株；

2、從一棵植株跳到前後左右與之相鄰的另一棵植株；

3、采摘一棵植株下的花生；

4、從最靠近路邊（即第一行）的某棵花生植株跳回路邊。

現在給定一塊花生田的大小和花生的分布，請問在限定時間内，多多最多可以采到多少個花生？注意可能隻有部分植株下面長有花生，假設這些植株下的花生個數各不相同。

例如在圖2所示的花生田裡，隻有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下長有花生，個數分别為13, 7, 15, 9。沿着圖示的路線，多多在21個機關時間内，最多可以采到37個花生。

輸入格式

第一行包括三個整數，M, NM,N和KK，用空格隔開；表示花生田的大小為M×N(1≤M,N≤20)，多多采花生的限定時間為K(0≤K≤1000)個機關時間。接下來的M行，每行包括N個非負整數，也用空格隔開；第i + 1行的第j個整數表示花生田裡植株(i, j)下花生的數目，0表示該植株下沒有花生。

輸出格式

一個整數，即在限定時間内，多多最多可以采到花生的個數。

題目連結

解題思路

這道題比較簡單，一開始想法有些複雜。題目中所謂地找到能采摘的最多花生數并不是最多的，而是在規定時間内，按照每次都去選擇剩餘位置中花生最多的位置的政策去采摘，本質上是一個貪心算法的思路。是以我的算法設計是這樣的：

（第一次用markdown畫流程圖，蠻有趣的。。。）

下面貼一下代碼：

#include<cstdio>
#include<cstdlib>
#include<iostream>
#define MAXSIZE 400

using namespace std;

typedef struct
{
	int count,x,y;
}peanut;

int solve_distance(peanut p1,peanut p2)
{
	return (abs(p1.x-p2.x)+abs(p1.y-p2.y));
}

int findmax(peanut field[],int length)
{
	int i = 0,max = 0,position=0;
	for(;i<length;i++)
	{
		if(field[i].count>max)
		{
			max = field[i].count;
			position = i;
		}
	}
	return position;
}
		

int main()
{
	int M, N, K;
	int i, j, index = 0, sum = 0, time = 0;
	int now_position, next_position;
	peanut field[MAXSIZE];
	cin >>M>>N>>K;
	int sumcount = M*N;
	for(i=1;i<=M;i++)
		for(j=1;j<=N;j++)
		{
			cin >>field[index].count;
			field[index].x = i;
			field[index].y = j;
			index++;
		}
	now_position = findmax(field,sumcount);
	next_position = now_position;
	time += (field[now_position].x + 1);
	
	while((time + field[next_position].x) <= K)
	{
		now_position = next_position;
		sum += field[now_position].count;
		
		//printf("%d %d",field[now_position].count,sum);
		
		field[now_position].count = 0;
		next_position = findmax(field,sumcount);
		time = time + solve_distance(field[now_position],field[next_position]) + 1 ;
		
		//printf(" %d\n",time);	
	}

	cout <<sum;
	//system("pause");
	return 0;
}
           

資料結構是用了一個結構體，用來儲存位置的坐标、花生數。整個花生田用一維結構體數組儲存。