C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 1740 蜂巢迷宫

题目

有一个无限大的蜂巢迷宫,为了方便表示每一个六边形格子,现在把座标引入到这个迷宫中,如上图年示。

艾瑞特在这个迷宫中街,刚开始他在(0,0)的位置,按照下图所示的路线在这个迷宫中行走。

走了n步以后,他想知道自己在哪个位置了。

思路

走1-6步1层,7-18步2层,二分查找层数,在最后一层6个if走6边

代码

c++ #include<bits/stdc++.h> #define ll long long #define db double using namespace std; ll n; int main(){ cin>>n; if(n==0){ cout<<"0 0\n"; return 0; } ll l=1,r=1e9,mid,lev; while(l<=r){ mid=(l+r)>>1; if(3*mid*(mid-1)<n){ l=mid+1; lev=mid; } else r=mid-1; } //cout<<lev<<endl; ll cx=-1+2*lev,cy=2; n-=3*lev*(lev-1);n--; if(n<=lev-1){ cx-=n,cy+=2*n; cout<<cx<<' '<<cy<<endl; return 0; } n-=(lev-1); cx-=(lev-1),cy+=2*(lev-1); if(n<=lev){ cx-=2*n; cout<<cx<<' '<<cy<<endl; return 0; } n-=lev; cx-=lev*2; if(n<=lev){ cx-=n,cy-=2*n; cout<<cx<<' '<<cy<<endl; return 0; } n-=lev; cx-=lev,cy-=2*lev; if(n<=lev){ cx+=n,cy-=2*n; cout<<cx<<' '<<cy<<endl; return 0; } n-=lev; cx+=lev,cy-=2*lev; if(n<=lev){ cx+=2*n; cout<<cx<<' '<<cy<<endl; return 0; } n-=lev; cx+=2*lev; if(n<=lev){ cx+=n,cy+=2*n; cout<<cx<<' '<<cy<<endl; return 0; } n-=lev; cx+=lev,cy+=2*lev; return 0; }

  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/58122/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!