# ICPC 训练赛 - Philosopher‘s Walk

# 题意

image-20210415121210364 image-20210415121231522

如图所示,给定这样的一个 n 阶图形,每次从左下角开始走,问走了 m 步后的位置坐标?

这个图是有规律可循的,定义 f (i) 是 i 阶图的样子,那么 f (i+1) 就是四个 f (i) 拼成的,上面两个和 f (i) 一样,左下角是 f (i) 顺时针旋转 90 度得到,右下角是 f (i) 逆时针旋转 90 度得到,因此可以定一个 dfs 函数返回的是坐标,不管这个图形是否旋转,我们只求这个图形没有旋转,也就是正着放时走 m 步的坐标,即使它旋转了,这个坐标也只不过是换了一个角度而已,我们是知道图形的尺寸的,那就可以根据这个尺寸来推出这个点的坐标

# CODE

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=100010;
int n,m; 
pii dfs(int x){
	if(x==1) return {1,1};  // 一阶方阵直接返回坐标 (1,1)
	x/=2;  
	int res=x*x;  // 算出 1/4 的尺寸有多少个小方格
	if(m>3*res){  // 如果在第 4 个子图内
		m-=3*res;  // 减一下步数
		pii tmp=dfs(x);  // 得到在这个小子图 (正着放) 左下角开始跑 m 步的坐标
		return {x*2-tmp.second+1,x-tmp.first+1};  // 核心,尽管跑出来的是正着放的坐标,但是可以转化为在当前图形的坐标
	}
	else if(m>2*res){
		m-=2*res;
		pii tmp=dfs(x);
		return {x+tmp.first,x+tmp.second};
	}
	else if(m>res){
		m-=res;
		pii tmp=dfs(x);
		return {tmp.first,x+tmp.second};
	}
	else{
		pii tmp=dfs(x);
		return {tmp.second,tmp.first};
	}
}
int main(){
    cin>>n>>m;
    pii ans=dfs(n);
    cout<<ans.first<<' '<<ans.second<<'\n';
    return 0;
}
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝