POJ3889 Fractal Streets

题目地址
给你一个原始的分形图,t组数据,对于每组数据,输入3个数n,h,o
(n为在第n级,h,o为两个房子的编号)
求在第n级情况下,编号为h和o的两个点之间的距离*10为多少
其中,第n级分形图形成规则如下:

首先先在右下角和右上角复制一遍n-1情况下的分形图
然后将n-1情况下的分形图逆时针旋转90度,放到左上角
最后将n-1情况下的分形图顺时针旋转90度,放到左下角
按照上述规则形成n级分形图
编号是从左上角那个点开始计1,沿着道路计数
思想
本题的关键是求编号为M的房屋在N级城市中的位置，然后根据勾股定理求出两点的距离。
这是著名的分形图，因为按照一定的规律进行变换，使用递归是最佳的策略。
首先明确递归边界：当N=1时
若M=1,x=1,y=1
若M=2,x=1,y=2
若M=3,x=2,y=2
若M=4,x=2,y=1

设N级的规模为p[N]
之后，我们要写出递归式，来综合分析一下情况

若当前的编号小于上一级规模，则该点位于目前图的左上角。因为左上角是由上一规模旋转90度得到的，x和y要倒一下。递归式f(N-1,M,y,x)
编号小于2倍的上一级规模时，在右上角，没有旋转。因为根据上一级来推下一级，所以编号要减去上一级规模。在递归结束后，也要使x加上上一级边的大小。递归式f(N-1,M-p[N-1],x,y);x+=(1<<(N-1))
类比第二种情况，但是x,y都要加上上一级边的大小。递归式f(N-1,M-2*p[N-1],x,y);x+=(1<<(N-1));y+=(1<<(N-1));
最后一种情况，比较复杂。观察分形图，比较坐标。我们知道：x映射为(1<<N)+1-x y映射为(1<<(N-1))+1-y 递归式略

Code


#include <cstdio>
#include <cmath>
using namespace std;
long a[16],t;
void find(long level,long num,long &x,long &y){
 if(level==1){
  if(num==1)x=1,y=1;
  else if(num==2)x=1,y=2;
  else if(num==3)x=2,y=2;
  else x=2,y=1;
  return;
 }
 if(num<=a[level-1])find(level-1,num,y,x);
 else if(num<=a[level-1]*2){
  find(level-1,num-a[level-1],x,y);
  y+=(1<<(level-1));
 }
 else if(num<=a[level-1]*3){
  find(level-1,num-a[level-1]*2,x,y);
  x+=(1<<(level-1));
  y+=(1<<(level-1));
 }
 else if(num<=a[level]){
  find(level-1,num-a[level-1]*3,y,x);
  x=(1<<level)-x+1;
  y=(1<<(level-1))-y+1;
 }
}
int main(){
 a[0]=1;for(int i=1;i<=16;++i)a[i]=a[i-1]*4;
 scanf("%ld",&t);
 while(t--){
  long n,s,e,sx=0,sy=0,ex=0,ey=0;
  scanf("%ld%ld%ld",&n,&s,&e);
  find(n,s,sx,sy);
  find(n,e,ex,ey);
  printf("%.0f\n",sqrt((sx-ex)*(sx-ex)+(sy-ey)*(sy-ey))*10);
 }
}

注意:POJ上若要用cmath 则须用G++

思想

Code