$$FractalStreets$$

题目链接：POJ 3889

题目大意

给你一个原始的分形图,$t$组数据,对于每组数据,输入$3$个数$n$,$h$,$o$ 。
($n$为在第$n$级,$h$,$o$为两个房子的编号)
我们要求求在第$n$级情况下,编号为$h$和$o$的两个点之间的距离为多少。
（输出的值要四舍五入到整数）
其中,第$n$级分形图形成规则如下:

1. 在右下角和右上角复制一遍$n-1$情况下的分形图
2. 将$n-1$情况下的分形图逆时针旋转$90$度,放到左上角
3. 将$n-1$情况下的分形图顺时针旋转$90$度,放到左下角

编号是从左上角那个点开始计$1$,沿着道路计数。

（从左到右分别是一到三级的分形图，小正方形的边长为10，点在小正方形的正中央）

样例输入

3
1 1 2
2 16 1
3 4 33

样例输出

10
30
50

数据范围

$n<16$
$h,o<2^{31}$

思路

这道题要用递归$（dfs）$来做。
我们可以将第$n$级变成$4$个$n-1$级，然后判断我们要找的那个点在哪一个，然后一直递归下去，就可以找到编号点所对应的坐标了。
我们找到两个编号的坐标，就可以通过勾股定理求出距离了。

代码

#include<cstdio>
#include<cmath>
#define abs(x) (x)<0?0-(x):(x)
#define pow(x) (x)*(x)
#define ll long long
using namespace std;
int T,n;
ll h,o,xx,yy,xxx,yyy;
void place(int nn,ll num,ll &x,ll &y)
{
	if (nn==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 if (num==4)//右下角
		{
			x=2;
			y=1;
		}
		return ;
	}
	ll temp=(ll)1<<(2*nn-2);//计算出四个区的分界线
	if (num<=temp) place(nn-1,num,y,x);//左上角
	 else if (num<=2*temp)//右上角
	 {
		place(nn-1,num-temp,x,y);//递归
		y+=1<<(nn-1);//准确坐标
	 }
	  else if (num<=3*temp)//左下角
	  {
	  	place(nn-1,num-2*temp,x,y);//递归
	  	x+=1<<(nn-1);//准确坐标
	  	y+=1<<(nn-1);
	  }
	   else if (num<=4*temp)//右下角
	   {
	   	place(nn-1,num-3*temp,y,x);//递归
	   	x=(1<<nn)+1-x;//准确坐标
	   	y=(1<<nn-1)+1-y;
	   }
}
int main()
{
	scanf("%d",&T);//读入
	for (int i=1;i<=T;i++)
	{
		scanf("%d%lld%lld",&n,&h,&o);//读入
		place(n,h,xx,yy);//求出出发点坐标
		place(n,o,xxx,yyy);//求出终点坐标
		printf("%.0lf\n",sqrt((double)(pow(abs(xx-xxx))+pow(abs(yy-yyy))))*10);//勾股定理求出距离（记得乘10）
	}
	return 0;
}