[2016-2017 ACM-ICPC, South Pacific Regional Contest (SPPC 16)]A Anticlockwise Motion
Zarxdy34
posted @ 2017年10月11日 10:34
in Codeforces
with tags
模拟
, 780 阅读
求在一个32001*32001,中间为1,中心3*3为\[7 6 5\]\[8 1 4\]\[9 2 3\]的蛇形矩阵中,数字a,b的曼哈顿距离。
题解:注意到从1开始向左下角延伸依次为9,25,49,81,121,即奇数的平方,由此来进行模拟。
#include <bits/stdc++.h> using namespace std; int main() { int a,b,ma,mb,xa,ya,xb,yb; scanf("%d%d",&a,&b); ma=1; while (a>ma*ma) ma+=2; xa=ya=16002-(ma+1)/2; if (ma*ma-ma<a) ya+=ma*ma-a; else { ya+=ma-1; if (ma*ma-ma*2+1<a) xa+=ma*ma-ma+1-a; else { xa+=ma-1; if (ma*ma-ma*3+2<a) ya-=ma*ma-ma*2+2-a; else { ya-=ma-1; xa-=ma*ma-ma*3+3-a; } } } mb=1; while (b>mb*mb) mb+=2; xb=yb=16002-(mb+1)/2; if (mb*mb-mb<b) yb+=mb*mb-b; else { yb+=mb-1; if (mb*mb-mb*2+1<b) xb+=mb*mb-mb+1-b; else { xb+=mb-1; if (mb*mb-mb*3+2<b) yb-=mb*mb-mb*2+2-b; else { yb-=mb-1; xb-=mb*mb-mb*3+3-b; } } } printf("%d\n",abs(xa-xb)+abs(ya-yb)); return 0; }