BNUOJ - 4049 - 사지 수

사지 수 트 리 시간 제한: 1000 ms 메모리 제한: 65536 KB 64 비트 정수 IO 형식:% lld Java 클래스 이름: Main Prev Submit Status Statistics 토론 다음 유형: 없 음
Tag it! 사지 수 는 자주 사용 하 는 데이터 구조 로 그리드 데이터 (예 를 들 어 지도 데이터, 원 격 감지 이미지) 의 압축 코드 에 광범 위 하 게 응용 된다.사지 수 를 3 차원 으로 확장 하면 사지 수 를 형성 하여 3 차원 정보의 압축 저장 을 실현 할 수 있다.다음은 그것 의 실현 원리 이다.
그림 이 8 * 8 그림 인 경우 이 그림 의 모든 요소 가 같 으 면 0 으로 인 코딩 하고 공공 과 같은 요소 (예 를 들 어 01 또는 00) 를 추가 합 니 다.다 르 면 먼저 1 로 인 코딩 한 다음 그림 을 4 개 4 * 4 그림 으로 나 눕 니 다.이 작은 구역 에서 모든 픽 셀 이 같은 요소 일 때 까지 위의 작업 을 계속 합 니 다 (물론 마지막 에는 픽 셀 점 만 남 을 수 있 습 니 다).마지막 으로 (예 를 들 어 (d) 그림) 은 분 단 된 차원 에 따라 위 에서 아래로, 왼쪽 에서 오른쪽으로 모든 01 서열 을 연결 합 니 다.위의 그림 과 같이 이미지 의 인 코딩 은 1001010000101000100010001000100100001 입 니 다. 주의: 같은 차원 의 네 개의 작은 이미지 입 니 다. 합 친 순 서 는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 입 니 다. (d) 그림 과 같 습 니 다.이 문 제 는 학생 들 에 게 이 인 코딩 과정 을 실현 하고 출력 압축 후의 0 - 1 서열 을 프로 그래 밍 하도록 요구한다.
Input 입력 첫 번 째 줄, 하나의 정수 n 은 반드시 2 의 멱 (2, 4, 8, 16 등) 이 고 최대 16 을 초과 하지 않 으 며 다음은 n * n 의 01 행렬 이 며 행렬 의 요 소 는 0 과 1 에 불과 합 니 다.
Output 출력 압축 후의 01 시퀀스, 하나의 문자열, 0 과 1 만 있 습 니 다.
Sample Input 8 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
샘플 출력 100101000010001000100010001000100010001000100100001 Source 중국지질대학 (북경) 제3 회 프로 그래 밍 경연 대회
사지 수 를 만 들 고 유지 할 수 있 습 니 다.샅 샅 이 뒤 지 는 방법 으로오십 여 줄 을 샅 샅 이 뒤지다

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<string.h>
#include<ctype.h>
using namespace std;
const int maxn=18;
int map[maxn][maxn];
string str[maxn];
int n;
bool check(int x,int y,int flag)
{
    for(int i=0; i<flag; ++i)
        for(int j=0; j<flag; ++j)
            if(map[x+i][y+j]!=map[x][y])
                return false;
    return true;
}
void DFS(int x,int y,int flag,int deep)//       ，      ，    
{
    string temp="1";
    if(check(x,y,flag))
    {
        temp="0";
        if(map[x][y]==0)
            temp+="0";
        else
            temp+="1";
        str[deep]+=temp;
        return;
    }
    str[deep]+=temp;
    DFS(x,y,flag>>1,deep+1);
    DFS(x,y+(flag>>1),flag>>1,deep+1);
    DFS(x+(flag>>1),y,flag>>1,deep+1);
    DFS(x+(flag>>1),y+(flag>>1),flag>>1,deep+1);
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
                scanf("%d",&map[i][j]);
        for(int i=0; i<maxn; ++i)
            str[i]="";
        DFS(0,0,n,0);
        for(int i=0; i<=log2(n); ++i)
            cout<<str[i];
        cout<<endl;
    }
    return 0;
}

세우다http://blog.csdn.net/wr_technology/article/details/51204075