From 8482680ad68093fa56d10364f591764250c0c2f0 Mon Sep 17 00:00:00 2001
From: Iru Cai <mytbk920423@gmail.com>
Date: Tue, 17 Apr 2018 16:34:59 +0800
Subject: 2.1 castle, frac1

---
 2.1/castle.c | 149 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 149 insertions(+)
 create mode 100644 2.1/castle.c

(limited to '2.1/castle.c')

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;
+}
-- 
cgit v1.2.3