Philosopher’s Walk

题意：

给你n和m，问你n*n的矩形中，数字m的位置

思路：

递归？！

有点分块的意思其实o(︶︿︶)o

对一个大的正方形，分成上下左右的四个部分，你需要确定m在哪个块里面，然后对这个块再次进行分块，一直找到最后

写成递归的形式，递归的变量是此时的正方形边长n，和对于n*n的正方形我们需要找到的数m，对于每次找到了数m所在的小正方形，我们就可以进行下一次递归，递归的变量是要缩小的，所以再递归后面得把数据加回来，这样等return的时候就一步步加出答案

现在我们来确定递归的结束条件：

当n=2，也就是分块分到最后剩下一个正方形，此时我们就可以根据此时的m确定是四个小正方形的哪一个，有了小正方形的位置，我们就可以看图知道其x和y，就开始return了

再来确定递归的四种情况：

首先，我们观察图可以发现，数其实有一个大的方向，就是从（1，1，）->（1，2）->（2，2）->（2，1）数再变大，且分割点是与n*n对应的四等分点

情况一：

m <= n * n / 4，此时点大概在图形的左下角，我们就应该去dfs左下角，对于dfs的第一个变量n是原来的n / 2，第二个变量m有点不同¯ \ _ (ツ) _ / ¯，

我们看图说话

n每放大一倍，第一象限和第四象限就会逆时针旋转90度，所以我们得处理这个m，新的m = $n * n / 4 - m + 1$（别问，问就是看题解抄的公式(>_<)）

所以对于第一象限的我们需要

dfs(n / 2, n * n / 4 - m + 1);

到这里我们就进入了下层递归，在上面说了，我们改变了m的值，其对于的x和y的值也改变了，我们得改回来

这个图案是相当于原地旋转90度，由(x0,y0)变到(x0',y0')，这里先给出求旋转后的坐标的方法：

先互换x和y的坐标，新的坐标的x0' = y0, y0' = 边长 + 1 – x

现在给出证明：

我们对这个正方形进行原地旋转，我们设左上角的点为（x0， y0），则旋转后的为点（x0', y0')，看图我们可以发现，原来的y轴经由平移后就是新的x轴，也就是原来的纵坐标等于现在的横坐标。而现在的纵坐标加上原来的横坐标等于边长

所以x0' = y0, y0' = 变长 + 1 – x0

就可以写成这个样子：

dfs(n/2,n*n/4-m+1);
swap(x,y);
y=n/2+1-y;

情况二：

n * n / 4< m <= n * n / 2,也就是左上角的第二象限，看图可以发现，其形状没有变化，没有出现像第一种情况的旋转，我们就可以当作把他向下平移到左下角，此时m的变化就很简单了，直接减去第一象限的数即可，也就是直接dfs(n / 2, m – n * n / 4)，因为相当于向下平移，x值不变，y值减少了n / 2，所以得加回来

dfs(n/2,m-n*n/4);y+=n/2;

情况三：

n * n / 2 < m <= n * n * 3 / 4, 也就是右上角第三象限，同样的看图发现形状没有变化，同情况二

dfs(n/2,m-n*n/2);x+=n/2;y+=n/2;

情况四：

n * n * 3 / 4 < m <= n * n ,也就是右下角，看图可以发现，是将n / 2为边长的图形逆时针原地旋转90度，和情况一类似，不过这次是

dfs(n / 2, n * n – m + 1)

y0' = x0, x0' = 边长 + 1 – y0

dfs(n/2,n*n-m+1);swap(x,y);x=n/2+1-x;x+=n/2;

给出标程码：

#include <bits/stdc++.h>
using namespace std;
int x,y;
void dfs(int n,int m)
{
    if (n==2)
    {
        if (m==1) x=y=1;
        else if (m==2){ x=1;y=2;}
        else if (m==3) {x=y=2;}
        else {x=2;y=1;}
        cout<<x<<' '<<y<<endl;
        return;
    }
    if (m<=n*n/4){dfs(n/2,n*n/4-m+1);swap(x,y);y=n/2+1-y;cout<<x<<' '<<y<<endl;}
    else if (m<=n*n/2) {dfs(n/2,m-n*n/4);y+=n/2; cout<<x<<' '<<y<<endl;}
    else if (m<=n*n/4*3){ dfs(n/2,m-n*n/2);x+=n/2;y+=n/2;cout<<x<<' '<<y<<endl;}
    else {dfs(n/2,n*n-m+1);swap(x,y);x=n/2+1-x;x+=n/2;cout<<x<<' '<<y<<endl;}
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    dfs(n,m);
    printf("%d %d\n",x,y);
    return 0;
}

这题折磨了我一个晚上，脑子里全是递归，旋转，坐标(╥﹏╥)