首页 > 代码库 > UVa 808 (建坐标系、找规律) Bee Breeding
UVa 808 (建坐标系、找规律) Bee Breeding
题意：
如图，按照图中的规律给这些格子编号。给出两个格子的编号，求从一个格子到另一个格子的最少步数。(一步只能穿过有有公共边的格子)
分析：
根据高中数学知识，选任意两个不共线的向量，就能表示平面上所有点。
像这样建立坐标系，根据图中的规律算出所有点的坐标。
推理也好，找找规律也好，不难发现
- 第一、三象限的点(x, y)到原点的距离为 |x| + |y|
- 第二、四象限的点(x, y)到原点的距离为 max{|x|, |y|}
递推点的坐标的时候也是比较注意细节的，否则很容易出错。
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 using namespace std; 5 const int maxn = 10000; 6 7 struct Point 8 { 9 int x, y;10 Point(int x=0, int y=0):x(x), y(y) {}11 }p[maxn + 330];12 13 int dx[] = {-1, -1, 0 , 1 , 1 , 0 }; //六个方向14 int dy[] = {0 , 1 , 1 , 0 , -1, -1};15 int pos;16 17 void cal(int dir, int l) //按照dir方向递推l个格子的坐标18 {19 pos++;20 while(l--)21 {22 p[pos] = Point(p[pos-1].x+dx[dir], p[pos-1].y+dy[dir]);23 pos++;24 }25 pos--;26 }27 28 void Init()29 {30 p[2] = Point(1, -1);31 pos = 2;32 for(int l = 1; l <= 58; ++l)33 {34 for(int dir = 0; dir < 4; ++dir)35 cal(dir, l);36 cal(4, l+1);37 cal(5, l);38 }39 }40 41 int main()42 {43 Init();44 45 int n, m;46 while(scanf("%d%d", &n, &m) == 2 && n)47 {48 int x = p[n].x - p[m].x;49 int y = p[n].y - p[m].y;50 int ans;51 if((x<0&&y>0) || (x>0&&y<0)) ans = max(abs(x), abs(y));52 else ans = abs(x+y);53 54 printf("The distance between cells %d and %d is %d.\n", n, m, ans);55 }56 57 return 0;58 }
UVa 808 (建坐标系、找规律) Bee Breeding
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。