gistfile1.txt

#include <stdio.h>
#include <malloc.h>

const int LIMIT = 30;
const int INF = 876543210;

typedef struct {
	int x;
	int y;
} pos_t;

typedef struct {
	int width;
	int height;
	int isBad[LIMIT * LIMIT];
} rawpanel_t;

typedef struct {
	int width;
	int height;
	int currentSum[LIMIT * LIMIT];
} panel_t;

void getPanelFromRaw(rawpanel_t* src);
int getMinimumCost(rawpanel_t* panel, register int designatedPixels);
int getBadPixels(register pos_t pos1, register pos_t pos2);
int getCost(register pos_t pos1, register pos_t pos2);

rawpanel_t rawpanel;
panel_t panel;

int main() {
	int currentCount, cases;
	int designatedPixels;
	scanf("%d", &cases);
	currentCount = 0;
	while (++currentCount <= cases) {
		scanf("%d %d %d", &rawpanel.height, &rawpanel.width, &designatedPixels);
		for (int y = 0; y < rawpanel.height; ++y) {
			for (int x = 0; x < rawpanel.width; ++x) {
				scanf("%d", &rawpanel.isBad[(y * rawpanel.width) + x]);
			}
		}
		printf("#testcase%d\n", currentCount);
		printf("%d\n", getMinimumCost(&rawpanel, designatedPixels));
	}
	return 0;
}

void getPanelFromRaw(rawpanel_t* src) {
	int currentPos;
	register int rowSum;
	register int width = panel.width = src->width;
	register int height = panel.height = src->height;
	register int* currentSum = &panel.currentSum[0];
	register int* currentPoint = &src->isBad[0];
	for (register int y = 0; y < height; ++y) {
		rowSum = 0;
		for (register int x = 0; x < width; ++x) {
			rowSum += *currentPoint;
			if (y)
				*currentSum = *(currentSum - width) + rowSum;
			else
				*currentSum = rowSum;
			++currentSum;
			++currentPoint;
		}
	}
}

int getMinimumCost(rawpanel_t* rawpanel, register int designatedPixels) {
	register pos_t leftUpPos;
	register pos_t rightDownPos;
	register int currentCost;
	register int badPixels;
	int width = rawpanel->width;
	int height = rawpanel->height;
	int minimumCost = INF;
	getPanelFromRaw(rawpanel);
	for (rightDownPos.x = width - 1; rightDownPos.x >= 0; --rightDownPos.x) {
		for (rightDownPos.y = height - 1; rightDownPos.y >= 0; --rightDownPos.y) {
			for (leftUpPos.x = 0; leftUpPos.x <= rightDownPos.x; ++leftUpPos.x) {
				for (leftUpPos.y = 0; leftUpPos.y <= rightDownPos.y; ++leftUpPos.y) {
					badPixels = getBadPixels(leftUpPos, rightDownPos);
					if (badPixels <= designatedPixels) {
						currentCost = getCost(leftUpPos, rightDownPos);
						if (currentCost < minimumCost)
							minimumCost = currentCost;
					}
				}
			}
		}
	}
	return minimumCost;
}

int getBadPixels(register pos_t pos1, register pos_t pos2) {
	register int result = 0;
	if (pos1.x && pos1.y) {
		result += panel.currentSum[((pos1.y - 1) * panel.width) + (pos1.x - 1)];
	}
	if (pos1.y) {
		result -= panel.currentSum[((pos1.y - 1) * panel.width) + pos2.x];
	}
	if (pos1.x) {
		result -= panel.currentSum[(pos2.y * panel.width) + (pos1.x - 1)];
	}
	result += panel.currentSum[(pos2.y * panel.width) + pos2.x];
	return result;
}

int getCost(register pos_t pos1, register pos_t pos2) {
	int result = 0;
	pos2.x = panel.width - pos2.x - 1;
	pos2.y = panel.height - pos2.y - 1;
	if (pos1.x < pos2.x)
		result += (pos1.x * 2) + pos2.x;
	else
		result += (pos2.x * 2) + pos1.x;
	if (pos1.y < pos2.y)
		result += (pos1.y * 2) + pos2.y;
	else
		result += (pos2.y * 2) + pos1.y;
	return result;
}