商汤科技2018校招C /算法开发/大数据/后端/运维/测试/数据挖掘开发工程师笔试第一场

#include<iostream>
#include<string>
using namespace std

const int MAX_SIZE = 1000
int n, m, k
int a[MAX_SIZE][MAX_SIZE]
int sum

void dfs(int  x,  int  y) {
	++sum
	a[x][y] = 1
	if ((x > 1) && (a[x-1][y] == 0)) dfs(x - 1, y)
	if ((y > 1) && (a[x][y-1] == 0)) dfs(x, y - 1)
	if ((x < n) && (a[x+1][y] == 0)) dfs(x + 1, y)
	if ((y < m) && (a[x][y+1] == 0)) dfs(x, y + 1)
}


int main( ) {
	memset(a, 0, sizeof(a))
	cin >> n >> m >> k
	for(int i = 1 i <= k ++i) {
		int x, y
		cin >> x >> y
		a[x][y] = 1
	}
	int ans = 0, ansp = 0
	for (int i = 1 i <= n ++i)
		for (int j = 1 j <= m ++j)
			if (a[i][j] == 0) {
				++ansp
				sum = 0
				dfs(i, j)
				if (ans < sum) ans = sum
			}
	cout << ans << " " << ansp << endl
	return  0
}

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了N堆。果园是一个二维平面，第i堆果子的位置为(X_i,Y_i)，重量为W_i。

多多决定把所有的果子合成一堆。每一次合并，多多可以消耗W_i (|X_i - X_j |+|Y_i - Y_j |)的体力把第i堆果子合并到第j堆。可以看出，所有的果子经过N-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

请你求出将所有果子合并成一堆消耗的总体力最少是多少。