Created
July 21, 2017 15:53
-
-
Save ebangin127/4dc04ca916f322c368af0d264373fadf to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment