分析:一开始觉得应该是可以递归,即图形N是由5个图形N-1拼出来的,N=1时就是一个'X',然后写着写着发现不太好把5个图形拼起来(就是行列的变化不太好处理),但是应该这个想法是没错的,只是我代码能力不强,写不出来.
然后又可以根据样例发现图形的另一个性质,其实可以把图形N看做一个边长为(3^{N-1})的正方形,正方形的每个格子是空格或者'X',这样我们就可以一行一行地处理下去,不用考虑上面那种方法中的复杂的行列号变换.
具体来说,我们每次DFS(其实还是递归),对于图形N,我们层层递归下去,每次求出图形N-1的5个小块中为'X'的格子标记就行了.最后一起按照行号来输出即可.
写到这里,我发现其实这两种方法的核心一样,只是一个是想一块一块来输出,一个是一块一块来处理然后一行一行来输出.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
int Base[10],visit[2200][2200];
inline void dfs(int n,int x,int y){
if(n==1){visit[x][y]=1;return;}
int m=Base[n-1];
dfs(n-1,x,y);
dfs(n-1,x+2*m,y);
dfs(n-1,x+m,y+m);
dfs(n-1,x,y+2*m);
dfs(n-1,x+2*m,y+2*m);
}
inline void solve(int n){
int m=Base[n];
for(int i=1;i<=m;++i)
for(int j=1;j<=m;++j)
visit[i][j]=0;
dfs(n,1,1);
for(int i=1;i<=m;++i){
for(int j=1;j<=m;++j){
if(visit[i][j])printf("X");
else printf(" ");
}
printf("
");
}
printf("-
");
}
int main(){
Base[1]=1;for(int i=2;i<=7;++i)Base[i]=Base[i-1]*3;
while(1){int n=read();if(n==-1)break;solve(n);}
return 0;
}