UVA ~ 297 ~ Quadtrees(4분 트리)

제목: 그림6-8에서 보듯이 4분의 나무로 흑백 이미지를 표시할 수 있다. 방법은 뿌리 결점으로 전체 이미지를 표시한 다음에 행렬을 두 등급으로 나누어 그림의 방식에 따라 번호를 매기고 왼쪽에서 오른쪽으로 네 개의 하위 결점에 대응하는 것이다.만약에 어떤 하위 결점에 대응하는 나머지 흰색 또는 검은색을 취하면 검은색 결점이나 흰색 결점으로 표시한다. 만약에 검은색과 흰색이 있다면 회색 결점으로 표시하고 이 구역을 귀속시키기 위해 나무를 세운다.
두 그루의 4분의 트리를 먼저 훑어보고 양자 합병 후 (검은색 부분 합병) 검은색 픽셀의 개수를 구한다.p는 중간 결점을 나타내고 f는 검은색(full), e는 흰색(empty)을 나타낸다.
각 그림의 크기는 32*32이며 검은색 블록의 개수를 출력합니다.
사고방식: 그림이 매우 작아서 검은색을 모두 1로 하고 개수를 통계하면 된다.이 그림을 먼저 훑어보면 된다.네 개의 값을 반복합니다. 현재 문자열 위치 p, 현재 하위 트리 왼쪽 상단 좌표 (x, y), 현재 하위 트리 변의 길이 w입니다.

#include
using namespace std;
const int MAXN = 1200;// 2^10 ↑
char s[MAXN];
int MAP[35][35], p, cnt;// 2^5 ↑
void draw(int &p, int x, int y, int w)
{
    char ch = s[p++];
    if (ch == 'p')
    {
        draw(p, x, y+w/2, w/2);    // 1
        draw(p, x, y, w/2);        // 2
        draw(p, x+w/2, y, w/2);    // 3
        draw(p, x+w/2, y+w/2, w/2);// 4
    }
    else if (ch == 'f')
    {
        for (int i = x; i < x+w; i++)
        {
            for (int j = y; j < y+w; j++)
            {
                if (MAP[i][j] == 0) MAP[i][j] = 1, cnt++;
            }
        }
    }
}
int main()
{
    int T; scanf("%d", &T);
    while (T--)
    {
        memset(MAP, 0, sizeof(MAP)); cnt = 0;
        scanf("%s", s); p = 0;
        draw(p, 0, 0, 32);
        scanf("%s", s); p = 0;
        draw(p, 0, 0, 32);
        printf("There are %d black pixels.
", cnt);
    }
    return 0;
}
/*
3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe
*/

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

UVA ~ 699 ~ The Falling Leaves(이차수의 DFS)

제목: 두 갈래 나무를 한 그루 주면 매 결점마다 수평 위치가 있다. 왼쪽 결점은 왼쪽에 한 단위, 오른쪽 결점은 오른쪽에 한 단위이다.왼쪽에서 오른쪽으로 각 수평 위치의 모든 결점의 권한 값의 합을 출력합니다.그림...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

UVA ~ 297 ~ Quadtrees(4분 트리)

좋은 웹페이지 즐겨찾기