POJ 8463:Stupid cat Doge（附对角线翻折研究）

“ Ctrl AC！一起 AC！”

题目：忘题戳这

分析：

将地图逐层分开研究，递归到第零级后逐渐回溯后，会发现如下规律：

 

升级后若为第一区域，则新坐标为由原坐标沿主对角线翻折得到。

升级后若为第二区域，则新坐标为原坐标的纵坐标加上每个区块的边长。

升级后若为第三区域，则新坐标为原坐标的横纵坐标分别加上边长。

升级后若为第四区域，则新坐标为由原坐标沿副对角线翻折得到。

（注意房间号升级后的位置变化就能得出规律）

关于对角线翻折问题不清楚的可以参考博主的另一篇文章：

矩阵对角线翻折问题研究

思路：找到用分治找到猫狗的坐标，再勾股定理。

AC代码：

#include<iostream>
using namespace std;
void levelup(int i, long long sql, long long& x, long long& y) {long long prex = x, prey = y;switch (i) {//四种变化，已分析case 0:x = prey; y = prex; break;case 1:y += sql; break;case 2:x += sql; y += sql; break;case 3:x = prey; y = prex; x = sql -1 - x; y = sql - 1 - y;x += sql; break;}
}
void find(int n, long long cd, long long& x, long long& y) {if (n == 0) return;long long sq = pow(2, 2 * (n - 1));//sq指该级每个区块的面级int i;for (i = 0; i < 4; i++) {//（i+1）指处于第几块if ((i + 1) * sq >= cd) break; }find(n - 1, cd - i * sq, x, y);//将前面的块数减掉，就是降级处理levelup(i, sqrt(sq), x, y);//升级后的坐标变化，sqrt（sq）指区块边长
}
int main() {int t; cin >> t;while (t--) {int n; cin >> n;long long cat, dog; cin >> cat >> dog;long long x1 = 0, y1 = 0, x2 = 0, y2 = 0;find(n, cat, x1, y1);//找坐标find(n, dog, x2, y2);long long ans= round(sqrt(pow((x1 - x2) * 10, 2) + pow((y1 - y2) * 10, 2)));//勾股定理cout << ans << endl;}return 0;
}

感谢阅读！！！

“ Ctrl AC！一起 AC！”