問題内容等についてはこちら。
http://nabetani.sakura.ne.jp/hena/ord16lcove/
ビットマップデータにしました。
#include <stdio.h>
#define WIDTH (10)
#define HEIGHT (10)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define swap(type, a, b) {type t = (a); (a) = (b); (b) = t;}
void reverseX(int *m, int w, int h)
{ /* m[y] is bitmap data of x */
int x, y, r;
for (y = 0; y < h; y++) {
r = 0;
for (x = 0; x < w; x++) r = (r << 1) | ((m[y] >> x) & 1);
m[y] = r;
}
}
void reverseY(int *m, int h)
{
int y = h / 2;
while (--y >= 0) swap(int, m[y], m[h - 1 - y]);
}
int cut(int *m, int w, int h)
{ /* search a maximum rectangle area on 0 at the left upper corner */
int area = 0, x = w, y;
for (y = 0; y < h; y++) {
if (m[y] & ((1 << x) - 1)) {
area = max(area, x * y);
while (m[y] & ((1 << x) - 1)) x--;
}
}
return area;
}
int solve(char *data)
{
int m[HEIGHT] = {0}, x, y, w, h, area, c;
int min_x = WIDTH, min_y = HEIGHT, max_x = 0, max_y = 0;
for (; *data; data++) {
if (isdigit(*data)) {
x = *data - '0'; y = *++data - '0';
m[y] |= 1 << x;
min_x = min(min_x, x); min_y = min(min_y, y);
max_x = max(max_x, x); max_y = max(max_y, y);
}
}
w = max_x - min_x + 1; h = max_y - min_y + 1;
area = w * h;
if (area == 1) return 3;
for (y = 0; y < h; y++) m[y] = m[y + min_y] >> min_x; /* move origin */
c = cut(m, w, h); /* upper left corner */
reverseY(m, h); c = max(c, cut(m, w, h)); /* lower left corner */
reverseX(m, w, h); c = max(c, cut(m, w, h)); /* lower right corner */
reverseY(m, h); c = max(c, cut(m, w, h)); /* upper right corner */
return c > 0 ? area - c : area < WIDTH * HEIGHT ? area + 1 : 0;
}
void test(char *data, char *correct)
{
int answer = solve(data);
printf("%s %d %s %s\n", answer==atoi(correct)?"OK":"NG", answer, correct, data);
}
int main()
{
/*0*/ test( "41,33,26,55,74,58,68", "39" );
/*1*/ test( "00,99,09,90", "-" );
/*2*/ test( "09", "3" );
/*3*/ test( "05,05,05", "3" );
/*4*/ test( "45", "3" );
/*5*/ test( "38,39", "3" );
/*6*/ test( "38,47", "3" );
/*7*/ test( "45,66", "4" );
/*8*/ test( "12,34,56,78", "33" );
/*9*/ test( "12,34,56,78,45", "37" );
/*10*/ test( "00,09,00", "11" );
/*11*/ test( "00,90", "11" );
/*12*/ test( "99,09", "11" );
/*13*/ test( "99,90", "11" );
/*14*/ test( "11,12,21,22", "5" );
/*15*/ test( "42,45,92,95,83,62", "25" );
/*16*/ test( "42,45,92,83,62", "14" );
/*17*/ test( "34,38,78,74,56,35,77,48,54", "26" );
/*18*/ test( "38,78,74,56,35,77,48,54", "23" );
/*19*/ test( "31,41,21,71,21", "7" );
/*20*/ test( "46,45,42,44,45", "6" );
/*21*/ test( "00,99,09", "19" );
/*22*/ test( "99,09,90,24", "64" );
/*23*/ test( "99,16,61,34,17,24,42,26,18,71,19,91,81,43,33,62,52,25", "75" );
/*24*/ test( "55,43,16,91,61,19,24,18,33,34,71,81,42,62,52,26,17,25", "53" );
/*25*/ test( "71,26,81,62,17,16,25,42,33,52,19,18,91,24,61,34,43", "45" );
/*26*/ test( "39,49,19,93,78,58,48,91,95,29,68,92,86,87,94,77", "39" );
/*27*/ test( "69,89,25,26,58,12,37,36,68,24,11,13,48,14,79", "37" );
/*28*/ test( "58,67,92,38,83,29,91,76,84,57,75,48,85,19,66", "51" );
/*29*/ test( "00,83,76,85,48,19,75,29,92,57,66,67,91,58,38,84", "91" );
/*30*/ test( "11,92,57,38,58,66,91,67,84,48,83,19,75,85,76,29", "72" );
/*31*/ test( "36,07,45", "9" );
/*32*/ test( "57,23,24,74", "21" );
/*33*/ test( "92,20,32,12,65", "39" );
/*34*/ test( "24,54,66,48,54,15", "21" );
/*35*/ test( "05,17,42,20,48,22,13", "39" );
/*36*/ test( "53,84,55,56,25,14,84,43", "26" );
/*37*/ test( "06,77,56,59,15,24,09,66,71", "51" );
/*38*/ test( "53,36,47,45,45,67,66,46,63,75", "21" );
/*39*/ test( "35,53,93,33,02,84,83,48,54,32,28", "50" );
/*40*/ test( "55,74,32,84,41,64,24,44,15,14,26,53", "39" );
/*41*/ test( "47,60,34,32,19,67,24,83,94,38,47,05,79", "88" );
/*42*/ test( "63,32,42,74,66,64,35,41,74,25,48,62,44,54", "42" );
/*43*/ test( "00,86,16,19,09,92,51,10,68,23,14,63,21,46,03", "91" );
/*44*/ test( "56,46,54,14,15,25,53,84,58,85,44,37,54,76,26,76", "42" );
/*45*/ test( "71,87,39,43,76,38,91,69,98,33,43,26,56,69,73,52,89", "66" );
/*46*/ test( "43,26,84,64,52,48,36,23,66,53,41,57,76,36,84,57,35,41", "47" );
/*47*/ test( "81,02,85,93,36,46,80,27,72,28,02,99,13,41,36,40,18,97,38", "91" );
/*48*/ test( "63,46,75,58,42,26,58,37,14,75,35,63,32,36,52,46,85,14,48,23", "47" );
/*49*/ test( "66,92,64,12,17,33,10,28,75,05,81,05,42,86,52,57,56,78,87,81,10", "82" );
/*50*/ test( "48,25,58,76,15,74,43,44,24,62,33,67,34,34,42,48,37,33,51,43,46,67", "50" );
return 0;
}