diff options
Diffstat (limited to '2.1/castle.c')
-rw-r--r-- | 2.1/castle.c | 149 |
1 files changed, 149 insertions, 0 deletions
diff --git a/2.1/castle.c b/2.1/castle.c new file mode 100644 index 0000000..3ac393c --- /dev/null +++ b/2.1/castle.c @@ -0,0 +1,149 @@ +/* +ID: mytbk921 +LANG: C +TASK: castle +*/ + +#include <stdio.h> +#include <string.h> + +struct module +{ + int component; + unsigned char walls; +}; + +struct wall +{ + int x, y; + char dir; + int comp[2]; +}; + +struct module castle[50][50]; +int col, row; + +#define FILL(i, j, c) castle[i][j].component=c;flood_fill(i,j); + +void flood_fill(int i, int j) +{ + unsigned char w = castle[i][j].walls; + int c = castle[i][j].component; + + if (j>0 && (w&1)==0 && castle[i][j-1].component==-1) { + FILL(i, j-1, c); + } + + if (i>0 && (w&2)==0 && castle[i-1][j].component==-1) { + FILL(i-1, j, c); + } + + if (j<col-1 && (w&4)==0 && castle[i][j+1].component==-1) { + FILL(i, j+1, c); + } + + if (i<row-1 && (w&8)==0 && castle[i+1][j].component==-1) { + FILL(i+1, j, c); + } +} + +int main() +{ + int i, j; + int ncomp; + int comp_area[2500]; + int max_area; + int nwalls = 0; + struct wall walls[10000]; + int max_area_created; + int wall_to_break; + + FILE *fin = fopen("castle.in", "r"); + FILE *fout = fopen("castle.out", "w"); + + fscanf(fin, "%d%d", &col, &row); + for (i=0; i<row; i++) { + for (j=0; j<col; j++) { + fscanf(fin, "%hhd", &castle[i][j].walls); + castle[i][j].component = -1; + } + } + fclose(fin); + + /* step 1: flood fill */ + ncomp = 0; + for (i=0; i<row; i++) { + for (j=0; j<col; j++) { + if (castle[i][j].component == -1) { + castle[i][j].component = ncomp; + flood_fill(i, j); + ncomp++; + } + } + } + + memset(comp_area, 0, sizeof(int)*ncomp); + for (i=0; i<row; i++) { + for (j=0; j<col; j++) { + comp_area[castle[i][j].component]++; + } + } + max_area = comp_area[0]; + for (i=0; i<ncomp; i++) { + if (comp_area[i]>max_area) + max_area = comp_area[i]; + } + fprintf(fout, "%d\n%d\n", ncomp, max_area); + + /* step 2: find all the walls */ + for (i=0; i<row; i++) { + for (j=0; j<col; j++) { + int w = castle[i][j].walls; + if (j<col-1 && (w&4)) { + walls[nwalls].comp[0] = castle[i][j].component; + walls[nwalls].comp[1] = castle[i][j+1].component; + if (walls[nwalls].comp[0] != walls[nwalls].comp[1]) { + walls[nwalls].x = i+1; + walls[nwalls].y = j+1; + walls[nwalls].dir = 'E'; + nwalls++; + } + } + + if (i>0 && (w&2)) { + walls[nwalls].comp[0] = castle[i][j].component; + walls[nwalls].comp[1] = castle[i-1][j].component; + if (walls[nwalls].comp[0] != walls[nwalls].comp[1]) { + walls[nwalls].x = i+1; + walls[nwalls].y = j+1; + walls[nwalls].dir = 'N'; + nwalls++; + } + } + } + } + + max_area_created = -1; + for (i=0; i<nwalls; i++) { + int area = comp_area[walls[i].comp[0]] + comp_area[walls[i].comp[1]]; + if (area > max_area_created) { + max_area_created = area; + wall_to_break = i; + } else if (area == max_area_created) { + if (walls[i].y < walls[wall_to_break].y) + wall_to_break = i; + else if (walls[i].y == walls[wall_to_break].y + && walls[i].x > walls[wall_to_break].x) + wall_to_break = i; + else if (walls[i].y == walls[wall_to_break].y + && walls[i].x == walls[wall_to_break].x + && walls[i].dir == 'N') + wall_to_break = i; + } + } + fprintf(fout, "%d\n%d %d %c\n", max_area_created, + walls[wall_to_break].x, walls[wall_to_break].y, + walls[wall_to_break].dir); + fclose(fout); + return 0; +} |