2126.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 53 行

/*  This Code is Submitted by wywcgs for Problem 2126 on 2005-12-14 at 18:46:38 */ 
#include <cstdio>
#include <cstring>

const int MAX = 128;
const int INF = 200000000;

inline int abs(int);
int min(int*, int);

int main()
{
	int row[MAX], col[MAX], map[MAX][MAX];
	int w, h;
	int t, T, i, j;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		memset(row, 0, sizeof(row));
		memset(col, 0, sizeof(col));
		scanf("%d %d", &w, &h);
		for(i = 0; i < h; i++) {
			for(j = 0; j < w; j++) {
				scanf("%d", &map[i][j]);
				row[i] += map[i][j];
				col[j] += map[i][j];
			}
		}
		printf("%d blocks\n", min(row, h)+min(col, w));
	}
	
	return 0;
}

inline int abs(int a)
{
	return a > 0 ? a : -a;
}
int min(int* deliver, int n)
{
	int i, j, best = INF;
	for(i = 0; i < n; i++) {
		int d = 0;
		for(j = 0; j < n; j++) {
			d += abs(i-j)*deliver[j];
		}
		if(best > d) {
			best = d;
		}
	}
	return best;
}