JOJ-2165-Hilbert Curve

王朝other·作者佚名 2006-01-09

The pictures above are Hilbert curve.You can see a Hilbert curve with a certain recursion depth n is composed of four different Hilbert curves with a certain recursion depth n-1 and three segments.

For this problem, you are to output the Hilbert Curve up to a certain recursion depth, using just 'X'.Draw the smallest Hilbert curve (that is not divided any further) as follows: XXX

XXX

To see how to draw larger Hilbert curve, take a look at the sample output.

InputThe input contains several testcases. Each is specified by an integer n (1 < n < 9).

OutputFor each test case, output the Hilbert curve with the certain recursion depth n.The output must not contain any trailing blanks. Print an empty line after each test case.

Sample Input2

Sample OutputXXXXX X

X X X

XXX XXX

X X X

XXXXX X

XXXXX XXXXX XXX

X X X X X

XXX XXX XXX XXX

X X X

XXX XXX X XXX X

X X X X X X X

XXXXX X XXX XXX

X X X X X X X

XXX XXX X XXX X

X X X

XXX XXX XXX XXX

X X X X X

XXXXX XXXXX XXX

#include<iostream>

using namespace std;

void main()

{

int lines[9];

lines[0]=1;

for(int i=1;i<9;i++)

lines[i]=lines[i-1]*2+1;

char Hilbert[520][520];

Hilbert[0][0]='X';

int r=1;

for(int i=1;i<9;i++)

{

for(int j=0;j<r;j++)

for(int k=0;k<r;k++)

{

Hilbert[j][r+1+k]=Hilbert[k][r-1-j];

Hilbert[r+1+j][k]=Hilbert[j][k];

Hilbert[r+1+j][r+1+k]=Hilbert[r-1-k][j];

}

Hilbert[0][r]='X';

Hilbert[r][r-1]='X';

Hilbert[2*r][r]='X';

r=r*2+1;

}

int n;

while(cin>>n)

{

for(int i=0;i<lines[n];i++)

{

int len=lines[n]-1;

while(Hilbert[i][len]!='X')

len--;

for(int j=0;j<=len;j++)

if(Hilbert[i][j]=='X')

cout<<Hilbert[i][j];

else

cout<<' ';

cout<<endl;

}

cout<<endl;

}

没有对数组进行初始化，如果全部先赋为空格反而会费时间在打印时判断更好