k線分形圖，【POJ3889】Fractal Streets（分形圖）

problem

• 給你一個原始的分形圖
• t組數據,對于每組數據,輸入3個數n,h,o (n為在第n級,h,o為兩個房子的編號)
• 求在第n級情況下,編號為h和o的兩個點之間的距離*10為多少

其中,第n級分形圖形成規則如下:
1. 首先先在右下角和右上角復制一遍n-1情況下的分形圖
2. 然后將n-1情況下的分形圖逆時針旋轉90度,放到左上角
3. 最后將n-1情況下的分形圖順時針旋轉90度,放到左下角
編號是從左上角那個點開始計1,沿著道路計數。

solution

遞歸邊界

當n等于1時(即是最初的那個第1級分形圖)1.當s等于1,x=1,y=12.當s等于2,x=1,y=23.當s等于3,x=2,y=24.當s等于4,x=2,y=1

遞歸過程

1.當前編號小于上一級編號總數時該情況說明當前編號是在n級分形圖的左上角,但是左上角分形圖是n-1級分形圖逆時針旋轉90度得到的顧我們帶入遞歸式時,需要將x和y,倒一下不明白的同學可以這樣看:第1級道路:(1,1)->(1,2)->(2,2)->(2,1)第2級道路左上角:(1,1)->(2,1)->(2,2)->(1,2)兩種情況的x和y情況互換了遞歸式: rec(n-1,s,y,x);2.當編號小于2倍的n-1數目時,說明當前編號s在分形圖的右上角由于右邊的分形圖沒有經過旋轉所以我們直接帶入遞歸式,需要注意的是我們的編號要減去上一級的編號,因為我們始終是根據上一級來推出下一級遞歸式:rec(n-1,s-p[n-1],x,y);遞歸出來之后,我們的x需要加上上一級的邊的大小這從分形圖中很容易看出即x=x+(1<<n-1);
3.當編號小于3倍的n-1數目時,跟第2種情況類似,只是遞歸出來之后,x和y都需要加上上一級的邊的大小即rec(n-1,s-2*p[n-1],x,y);//注意編號必須要小于上一級的大小// 因為我們是放在上一級的情況下考慮的x+=(1<<n-1);y+=(1<<n-1);
4.最后一種情況,s在第n級分形圖的左下角這種情況跟第2種情況差不多,我們先按照逆時針的情況來解決,這就跟第2種情況一樣了然后比較坐標x和y的關系,容易看出,順時針相比于逆時針x映射為(1<<n)+1-xy映射為(1<<(n-1))+1-y可以觀察分形圖,這個地方有點難理解可以比較坐標來理解

codes

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
void calc(int n, LL id, LL &x, LL &y){if(n == 1){if(id==1)x=1,y=1;if(id==2)x=1,y=2;if(id==3)x=2,y=2;if(id==4)x=2,y=1;}else{LL _id = (1<<(n-1))*(1<<(n-1));if(id <= _id){calc(n-1,id,y,x);}else if(id <= 2*_id){calc(n-1,id-_id,x,y);y += 1<<(n-1);}else if(id <= 3*_id){calc(n-1,id-2*_id,x,y);x += 1<<(n-1);y += 1<<(n-1);}else{calc(n-1, id-3*_id, y,x);x = (1<<n)+1-x;y = (1<<n-1)+1-y;}}
}int main(){int _w;  scanf("%lld", &_w);while(_w--){int n; LL h,o;scanf("%d%lld%lld", &n, &h, &o);LL sx, sy, ex, ey;calc(n,h,sx,sy);calc(n,o,ex,ey);printf("%.0f\n",sqrt((sx-ex)*(sx-ex)+(sy-ey)*(sy-ey))*10);}return 0;
}