Fractal-Streets

2023-12-13 20:45:35

title: Fractal Streets
date: 2023-12-13 14:48:45
tags: 分形
categories: 算法进阶指南

题目大意

将原来的城市复制一遍放在原城市的上方,将原城市顺时针90°放在原城市的左上方,将逆时针90°后的城市放在原城市的左边,然后用道路将四部分链接起来,反复进行相同操作。
在这里插入图片描述

解题思路

这是著名的通过一定规律无限包含自身的“分形”图。为了方便计算,我们把标号从 0 0 0 开始
解题关键就是,求编号为 M M M 的房屋在 N N N 级城市的位置,把问题转化为 calc(N,M),因此改题目转化为求 c a l c ( N , A ) calc(N,A) calc(N,A) c a l c ( N , B ) calc(N,B) calc(N,B) 的距离。
在求解 c a l c ( N , M ) calc(N,M) calc(N,M) 时,因为 N ? 1 N - 1 N?1 级城市有 2 2 ? N ? 2 2 ^ {2 * N - 2} 22?N?2 座房屋,所以我们先求解 c a l c ( N ? 1 , M m o d 2 2 ? N ? 2 ) calc(N - 1,M mod 2 ^ {2 * N - 2}) calc(N?1,Mmod22?N?2),根据房屋编号 M 与 该级数的房屋总数确定编号上下左右位置。
在这里插入图片描述

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1314;

const int MOD = 9901;

typedef pair<LL,LL> PII;

PII calc(LL n,LL m)
{
	if(n == 0) return make_pair(0,0);
	LL len = 1ll << (n - 1),cnt = 1ll << (2 * n - 2);//每一级的半长和多少个 1 级的 
	PII pos = calc(n - 1,m % cnt);
	LL x = pos.first, y = pos.second;
	LL z = m / cnt;
	if(z == 0) return make_pair(y,x);
	else if(z == 1) return make_pair(x,y + len);
	else if(z == 2) return make_pair(x + len,y + len);
	else  return make_pair(2 * len - y - 1,len - x - 1);
}
int main()
{
	int t; cin >> t;
	while(t --)
	{
		LL N,A,B;
		cin >> N >> A >> B;
		PII a = calc(N,A - 1),b = calc(N,B - 1);
		LL x = a.first - b.first, y = a.second - b.second;
		cout << fixed << setprecision(0) << sqrt(x * x + y * y) * 10 << endl; 
	} 
}

文章来源:https://blog.csdn.net/m0_73865722/article/details/134980934
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。