2018-03-17
蜂巢就是六边形的堆积，如何将蜂巢建图同时找到蜂巢的规律，就是本文要讨论的，在此，我引入了两道题，希望通过多角度的剖析，能让读者对此类题更加熟悉。
Bee Majia
题意：找到左右两图对应格子的数字关系，然后给你右图数字，输出该格子对应右图的数字。
方法一：找规律。
#include <stdio.h>
struct node{
int x,y;
node(){}
node(int a,int b){
x=a; y=b;
}
}a[100100];
int dir[5][2]={{-1,0},{0,-1},{1,-1},{1,0},{0,1}};
int main()
{
for(int i=1,j=1,k=0;i<100100;i+=j,j+=6,k++){
for(int m=0;m<k;m++){
a[i-m]=node(m,k-m);
}
a[i]=node(0,k);
int cur=i;
for(int m=0;m<5;m++){
for(int n=0;n<k;n++){
int xx=a[cur].x+dir[m][0];
int yy=a[cur].y+dir[m][1];
a[cur+1]=node(xx,yy);
cur++;
}
}
}
int n;
while(scanf("%d",&n)!=EOF){
printf("%d %d\n",a[n].x,a[n].y);
}
}
（建议将dir中的点在直角坐标系中表示出来，然后对应左图的坐标，就能发现规律。其中值得注意的是：k的作用是控制圈数，同时精髓就在第二个for中的第一语句和第二语句，这两个地方做到了特殊点特殊处理！！）
方法二：类似的找规律，但是没有打表。
#include<stdio.h>
#include<math.h>
int main(){
double x;
int n,t,p,x0,y0,i;
while(scanf("%d",&n)!=EOF){
x=(sqrt(12*n-3)-3)/6;
p=(int)x;
if(3*p*p+3*p+1!=n){
t=n-(3*p*p+3*p+1);
p++;
x0=p-1;
y0=0;
while(t){
t--;
y0++;
for(i=1;i<=p-1&&t;i++,t--)x0--,y0++;
for(i=1;i<=p&&t;i++,t--)x0--;
for(i=1;i<=p&&t;i++,t--)y0--;
for(i=1;i<=p&&t;i++,t--)x0++,y0--;
for(i=1;i<=p&&t;i++,t--)x0++;
for(i=1;i<=p&&t;i++,t--)y0++;
}
printf("%d %d\n",x0,y0);
}
else
printf("%d 0\n",p);
}
return 0;
}
这段代码取自随心所欲
Ta讲的非常详细了，在此并不赘述。其实思想都是一样的，不过我更喜欢方法一。
方法三：建立斜坐标系。
#include <iostream>
#include <math.h>
using namespace std;
#define eps 1e-6
#define zero(x) (((x)>0?(x):-(x))<eps)
int direct[6][2] = { { 0, 1 }, { -1, 1 }, { -1, 0 }, { 0, -1 }, { 1, -1 }, { 1, 0 } };//斜坐标系的六个方向
int main()
{
int x;
while (cin >> x)
{
double n = (sqrt(12 * x - 3)*1.0 - 3) / 6;
int p = zero(n - ceil(n)) ? (int) n : ceil(n);
int t = x - 3 * p * p + 3 * p - 1;
int xcord, ycord;
//x equals the n loops plus t.
//cout << (int) p << ' ' << t << endl;
xcord = p - 1; ycord = 0;
while (1)
{
if (t == 0) goto L1;//t==0就可以撤出来了~
xcord += direct[0][0], ycord += direct[0][1];//先向direct[0]走一步
t--;
if (t == 0) goto L1;
for (int i = 1; i <= p - 1; i++)
{
xcord += direct[1][0], ycord += direct[1][1];//再向direct[1]走p-1步
t--;
if (t == 0) goto L1;
}
for (int i = 2; i <= 6; i++)
{
for (int j = 1; j <= p; j++)
{
xcord += direct[i % 6][0], ycord += direct[i % 6][1];//然后向其他剩余的五个方向各走p步
t--;
if (t == 0) goto L1;
}
}
}
L1: cout << xcord << ' ' << ycord << endl;
}
}
dalao的代码，希望后面有机会能够用自己的语言改一下！挖坑X1；
简单dp（N=3样例情况）
看图就应该明白题意了。
本题的难点在于建图---输入一共有4*N-3行，要建成蜂巢状。
方法一：非递归。
#include<map>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define ll long long
#define maxn 100005
int n,dp[3205][2205],a[3205][2205];
int main(void)
{
scanf("%d",&n);int m=2*n-1;
memset(a, -62, sizeof(a));
for(int i=1;i<=4*n-3;i++)
{
int tmp;
if(i<=n) tmp=i;
else if(i>=4*n-3-n+1) tmp=4*n-3-i+1;
else tmp=n-((i-n)%2==1);
for(int j=m/2+2-tmp;j<=m/2+2-tmp+2*(tmp-1);j+=2)
scanf("%d",&a[i][j]);
}
memset(dp,-62,sizeof(dp));
for(int i=1;i<=4*n-3;i++)
for(int j=1;j<=m;j++)
{
if(i==1) dp[i][j]=a[i][j];
else if(a[i][j]>=-60000)
dp[i][j]=max(dp[i-1][j-1],max(dp[i-2][j],dp[i-1][j+1]))+a[i][j];
}
printf("%d\n",dp[4*n-3][n]);
return 0;
}
这是非递归建图的方法，其实很简单。
【
将此蜂巢分成三份，分别是 1...n，n-1和n交替出现，n...1。
】
方法二：递归。
此程序个人化非常严重，就不贴完全代码了。
void dfs(int x,int y,int n,int t)
{
if(!t) return ;
fup(i,0,n-1)
vis[x+2*i][y]=1;
dfs(x+1,y-1,n-1,t-1);
}
void dfs1(int x,int y,int n,int t)
{
if(!t) return ;
fup(i,0,n-1)
vis[x+2*i][y]=1;
dfs1(x+1,y+1,n-1,t-1);
}
for(int i=1;i<=4*n-3;i++){
for(int j=1;j<=2*n-1;j--)
if(vis[i][j]) scanf("%d",&a[i][j]);
q[i].push_back(j);
}
注：这里递归建图的时候是以列建图的。个人认为第二段代码不必用vector，与方法一采用类似的写法即可，在此再挖一坑。挖坑X2；
