2017-2018 ACM-ICPC, Asia Daejeon Regional Contest F（递推）

F题

Problem F Philosopher’s Walk

题意：给你n,m，n代表一个长宽都为2的n次方的格子里，m代表走了从左下角开始走了m米，求最后的坐标。

思路：

看上图很容易便可以看出规律，每幅图都是由上一幅图在自身的四个区域进行不同的变化的到的，如第二幅图中，第一区域是第一副图向左转90度得到的，第二第三区域都是横纵坐标偏移，第四区域是向右转90度且向右移动了一个区域。

那么就可以得出转移的规律：

第一区域：向左转90度只要每个点的横纵坐标互换即可如：2（2，1） 变成 2 （1，2）；

第二区域：向上移动一个区域的长度；

第三区域：向上移动一个区域，再向左移动一个区域。

第四区域，向右转90度x1,y1坐标变化为： x = k(一个区域的长度） - y1(原坐标）+ 1； y = k - x1 + 1;(先向左转90度，然后用k - 当前坐标就得到了向右移动90度的公式)，再向右移动一个区域的长度就可以了

按照这个规律一直递归推就可以了。

推的头皮发麻。。

实现代码：

#include
using namespace std;
struct node {int x,y;
};
node t;
node solve(int n,int m){if(n == 2){if(m==0){t.x = 1;t.y = 1;return t;}if(m == 1){t.x = 1;t.y = 2;return t;}if(m == 2){t.x = 2;t.y = 2;return t;}else{t.x = 2;t.y = 1;return t;}}int k = n/2;int x = m/(k*k);  //判断在上一幅图的哪一个区域if(x == 0){t = solve(k,m%(k*k));swap(t.x,t.y);return t;}if(x == 1){t = solve(k,m%(k*k));t.y += k;return t;}if(x == 2){t = solve(k,m%(k*k));t.x += k;t.y += k;return t;}if(x == 3){t = solve(k,m%(k*k));node t1 = t;t1.x = 2*k - t.y + 1;t1.y = k - t.x + 1;return t1;}
}int main()
{int n,m;cin>>n>>m;m--;node p = solve(n,m);cout<" "<endl;
}

转载于:https://www.cnblogs.com/kls123/p/8439078.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！