Submission #47343941

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int H, W;
char c[2048][2048];
int rowsum[2048][26], colsum[2048][26];
char rowdeleted[2048], coldeleted[2048];
int rowminus[26], colminus[26];
int rowdelnum, coldelnum;
int rowdellist[2048][2], coldellist[2048][2];
int main(void) {
  int i, j;
  int ans;
  if (scanf("%d%d", &H, &W) != 2) return 1;
  for (i = 0; i < H; i++) {
    if (scanf("%2047s", c[i]) != 1) return 1;
  }
  for (i = 0; i < H; i++) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

int H, W;
char c[2048][2048];

int rowsum[2048][26], colsum[2048][26];
char rowdeleted[2048], coldeleted[2048];

int rowminus[26], colminus[26];

int rowdelnum, coldelnum;
int rowdellist[2048][2], coldellist[2048][2];

int main(void) {
	int i, j;
	int ans;
	if (scanf("%d%d", &H, &W) != 2) return 1;
	for (i = 0; i < H; i++) {
		if (scanf("%2047s", c[i]) != 1) return 1;
	}
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			int idx = c[i][j] - 'a';
			if (0 <= idx && idx < 26) {
				rowsum[i][idx]++;
				colsum[j][idx]++;
			}
		}
	}
	for (;;) {
		rowdelnum = 0;
		coldelnum = 0;
		/* 各行および列について、印をつける条件を満たすかをチェックする */
		for (i = 0; i < H; i++) {
			if (!rowdeleted[i]) {
				int idx = -1;
				for (j = 0; j < 26; j++) {
					int curnum = rowsum[i][j] - rowminus[j];
					if (curnum > 0) {
						/* 1枚だけ or 他の色のクッキーがあった → 失格 */
						if (curnum == 1 || idx >= 0) {
							idx = -999;
							break;
						} else {
							idx = j;
						}
					}
				}
				if (idx >= 0) {
					rowdellist[rowdelnum][0] = i;
					rowdellist[rowdelnum][1] = idx;
					rowdelnum++;
				}
			}
		}
		for (i = 0; i < W; i++) {
			if (!coldeleted[i]) {
				int idx = -1;
				for (j = 0; j < 26; j++) {
					int curnum = colsum[i][j] - colminus[j];
					if (curnum > 0) {
						/* 1枚だけ or 他の色のクッキーがあった → 失格 */
						if (curnum == 1 || idx >= 0) {
							idx = -999;
							break;
						} else {
							idx = j;
						}
					}
				}
				if (idx >= 0) {
					coldellist[rowdelnum][0] = i;
					coldellist[rowdelnum][1] = idx;
					coldelnum++;
				}
			}
		}
		/* 印をつけたクッキーが無ければ終了 */
		if (rowdelnum == 0 && coldelnum == 0) break;
		/* 印をつけたクッキーを取り除く */
		for (i = 0; i < rowdelnum; i++) {
			rowdeleted[rowdellist[i][0]] = 1;
			colminus[rowdellist[i][1]]++;
		}
		for (i = 0; i < coldelnum; i++) {
			coldeleted[coldellist[i][0]] = 1;
			rowminus[coldellist[i][1]]++;
		}
	}
	/* 残ったクッキーの枚数を数える */
	ans = 0;
	for (i = 0; i < H; i++) {
		if (!rowdeleted[i]) {
			for (j = 0; j < 26; j++) {
				ans += rowsum[i][j] - rowminus[j];
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Judge Result