#include #include #include #define MAX_N_LENGTH 4 #define MAX_WIDTH 101 #define MAX_HEIGHT 100 #define PADDING MAX_WIDTH char input[PADDING + MAX_N_LENGTH + MAX_HEIGHT*MAX_WIDTH + PADDING]; int inputFront = -1+PADDING; int nLen, width; int N, N_2, count1, count2; short *queue; int queueFront, queueRear; short *areaBorder, *areaCheck; char *areaConnected; int currentArea, connectionCount; char output[5+1 + 5+1]; void redBFS(void) { queue[0] = inputFront; input[inputFront] = 'r'; int pos, newPosArr[4], newPos, area; queueFront = -1, queueRear = 0; while (queueFront < queueRear) { pos = queue[++queueFront]; newPosArr[0] = pos+1; newPosArr[1] = pos-1; newPosArr[2] = pos+width; newPosArr[3] = pos-width; for (int i = 0; i < 4; ++i) switch (input[newPos = newPosArr[i]]) { case 'R': queue[++queueRear] = newPos; input[newPos] = 'r'; break; case 'G': if (areaBorder[pos] != currentArea) areaBorder[pos] = currentArea; break; case 'g': area = areaBorder[newPos]; if (areaCheck[area] != currentArea && !areaConnected[area]) { ++connectionCount; areaCheck[area] = currentArea; areaConnected[area] = 1; } break; } } } void greenBFS(void) { queue[0] = inputFront; input[inputFront] = 'g'; int pos, newPosArr[4], newPos, area; queueFront = -1, queueRear = 0; while (queueFront < queueRear) { pos = queue[++queueFront]; newPosArr[0] = pos+1; newPosArr[1] = pos-1; newPosArr[2] = pos+width; newPosArr[3] = pos-width; for (int i = 0; i < 4; ++i) switch (input[newPos = newPosArr[i]]) { case 'G': queue[++queueRear] = newPos; input[newPos] = 'g'; break; case 'R': if (areaBorder[pos] != currentArea) areaBorder[pos] = currentArea; break; case 'r': area = areaBorder[newPos]; if (areaCheck[area] != currentArea && !areaConnected[area]) { ++connectionCount; areaCheck[area] = currentArea; areaConnected[area] = 1; } break; } } } void blueBFS(void) { queue[0] = inputFront; input[inputFront] = 'b'; int pos, newPos; queueFront = -1, queueRear = 0; while (queueFront < queueRear) { pos = queue[++queueFront]; if (input[newPos = pos+1] == 'B') queue[++queueRear] = newPos, input[newPos] = 'b'; if (input[newPos = pos-1] == 'B') queue[++queueRear] = newPos, input[newPos] = 'b'; if (input[newPos = pos+width] == 'B') queue[++queueRear] = newPos, input[newPos] = 'b'; if (input[newPos = pos-width] == 'B') queue[++queueRear] = newPos, input[newPos] = 'b'; } } void countArea(void) { int end = inputFront + N_2+N; while (++inputFront <= end) { switch (input[inputFront]) { case 'R': ++currentArea; redBFS(); break; case 'G': ++currentArea; greenBFS(); break; case 'B': ++currentArea; blueBFS(); break; } } count1 = currentArea, count2 = currentArea-connectionCount; } int main(void) { fread(&input[PADDING], sizeof(char), (MAX_N_LENGTH + MAX_HEIGHT*MAX_WIDTH) * sizeof(char), stdin); char c; while ((c = input[++inputFront]) > '0' && c <= '9') N = N*10 + c-'0'; width = N+1; memset(&input[PADDING], 0, (nLen = inputFront-(-1+PADDING)) * sizeof(char)); queue = malloc((N_2 = N*N) * sizeof(short)); areaBorder = calloc((-1+PADDING)+nLen + N_2+N, sizeof(short)); areaCheck = calloc(1+N_2, sizeof(short)); areaConnected = calloc(N_2, sizeof(char)); countArea(); output[11] = '\n'; int i = 11; do output[--i] = count2%10 + '0', count2 /= 10; while (count2); output[--i] = ' '; do output[--i] = count1%10 + '0', count1 /= 10; while (count1); fwrite(&output[i], sizeof(char), 12-i, stdout); free(queue), free(areaBorder), free(areaCheck), free(areaConnected); return 0; }

제출 #18810

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: