문명

- cnt를 vcnt로 계속 바꿔가면서 하면 매번 초기화 하지 않아도 된다.

               
#include <stdio.h>
 
/// *** user.cpp ***
#ifndef NULL
#define NULL 0
#endif // NULL
 
typedef unsigned long long ULL;
const ULL BASE = 199;
const int LM = 502;
const int MOD = 10007;
int N, M, A[LM][LM];
int visit[LM][LM], vcnt;
int dr[] = { -1, 0, 1, 0 }, dc[] = { 0, 1, 0, -1 };
int value[LM][LM];
ULL wei[16] = { 1 };
 
int ecnt;
struct Entry {
    int sr, sc;
    ULL key;
    void init() {
        key = 0;
    }
    void push(int r, int c) {
        init(); // 새좌표가 들어오면 init
        sr = r, sc = c; // 시작포인트 설정
        int i, nr, nc;
        for (i = 0; i < 4; ++i) {    // 상하좌우에 이어진 블럭이 있는지 확인
            nr = r + dr[i], nc = c + dc[i];
            if (A[nr][nc]) {
                value[r][c] += 1 << i;    // 현재 블럭 기준 어느쪽으로 이어졌는지를 현재 블럭에 추가
                value[nr][nc] += 1 << ((i + 2) & 3);  // 타겟 블럭 기준 현재블럭이 어느쪽인가를 타겟 블럭에 추가
            }
        }
    }
    void dfs(int r, int c) {
        if (visit[r][c] == vcnt || !A[r][c]) return;    // 이미 방문했거나 블럭값이 1이 아니면 리턴
        visit[r][c] = vcnt;     // 전역변수로 셀때마다 블럭 카운트를 증가하면서 해당 차수에서 간곳인지를 확인
        int rv = value[r][c];   // 해당 블럭의 스타일 값(상하좌우에 따른)
        key += wei[rv];         // hash key 업데이트
        for (int i = 0; i < 4; ++i) {    // dfs
            dfs(r + dr[i], c + dc[i]);
        }
    }
    int traverse() {
        if (visit[sr][sc] == vcnt) {
            printf("\ttraverse in and return r:%d, c:%d\n", sr, sc);
            return 1;   // 이번 차수에서 세어본 건 리턴
        }
 
        // 이 아래로 내려가는 케이스가 군집의 첫번째 좌표이다.
        // 이 군집에 다른것들이 달라 붙더라도 기준점은 이녀석이다.
        printf("\ttraverse in and go dfs r:%d, c:%d\n", sr, sc);
        init(); // 안 세어본거면 초기화하고 dfs돌리고 리턴
        dfs(sr, sc);
        return 0;
    }
}entry[10010];
 
int hcnt;
struct Hash {
    ULL key;
    int cnt;
    Hash*next;
    Hash*alloc(ULL nk, Hash*p) {
        key = nk, cnt = vcnt, next = p;
        return this;
    }
}hbuf[MOD], *htab[MOD];
 
void printmap()
{
    for (int i = 1; i <= M; ++i) {
        printf("\t");
        for (int j = 1; j <= N; ++j) {
            printf("%d", A[i][j]);
        }
        printf("\t");
        for (int j = 1; j <= N; ++j) {
            printf("%d", visit[i][j]);
        }
        printf("\n");
    }
}
 
void init(int row, int col) {
    N = row, M = col;
    vcnt = 0;
    ecnt = 0;       // 추가된 블럭 갯수 map에 1로 표시된거
    for (int i = 0; i < LM; ++i) {
        for (int j = 0; j < LM; ++j) {
            A[i][j] = visit[i][j] = 0;
            value[i][j] = 0;
        }
    }
    // 기본 weight 변수값 설정 1:199, 2:199*199, 3:199*199*199 ...
    for (int i = 1; i < 16; ++i) wei[i] = wei[i - 1] * BASE;
    hcnt = 0;
    for (int i = 0; i < MOD; ++i) {
        htab[i] = NULL;
    }
}
 
void addCivilization(int r, int c) {
    printf("addCivilization r:%d, c:%d\n", r,c);
    A[r][c] = 1;
    entry[++ecnt].push(r, c);
 
    for (int i = 1; i <= ecnt; ++i)  {
        printf("\tentry %d : s:%d, r:%d, key:%llu\n", 
            i, entry[i].sr, entry[i].sc, entry[i].key);
    }
    printf("addCivilization finish ecnt:%d\n\n", ecnt);
}
 
int countCivilization() {
    vcnt++;     // count함수 실행횟수
    printf("countCivilization vcnt:%d\n", vcnt);
    printmap();
    printf("========\n");
 
    int i;
    for (i = 1; i <= ecnt;) {
        printf("\t%d : count entry check r:%d, c:%d\n", i, entry[i].sr, entry[i].sc);
        if (entry[i].traverse()) {  // 이미 세어본거면 다음 entry로..
            entry[i] = entry[ecnt--];   // entry point 변경
        }
        else {
            i++;
        }
    }
 
    printmap();
    for (int i = 1; i <= ecnt; ++i)  {
        printf("\tentry %d : s:%d, r:%d, key:%llu\n",
            i, entry[i].sr, entry[i].sc, entry[i].key);
    }
 
    int ret = ecnt;
    for (i = 1; i <= ecnt; ++i) {
        ULL key = entry[i].key;
        int hidx = key % MOD;
        Hash*p = htab[hidx];
        for (; p; p = p->next) {
            if (p->key == key) break;
        }
        if (p == NULL) {
            htab[hidx] = hbuf[hcnt++].alloc(key, htab[hidx]);
        }
        else {
            if (p->cnt == vcnt) ret--; // 같은 모양
            p->cnt = vcnt;
        }
    }
 
    printf("\n");
    return ret;
}