2018-03-17
蜂巢就是六邊形的堆積护锤，如何將蜂巢建圖同時(shí)找到蜂巢的規(guī)律，就是本文要討論的怒详，在此炉媒，我引入了兩道題，希望通過(guò)多角度的剖析昆烁，能讓讀者對(duì)此類(lèi)題更加熟悉吊骤。
題意：找到左右兩圖對(duì)應(yīng)格子的數(shù)字關(guān)系，然后給你右圖數(shù)字善玫，輸出該格子對(duì)應(yīng)右圖的數(shù)字水援。
方法一：找規(guī)律。
#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中的點(diǎn)在直角坐標(biāo)系中表示出來(lái)茅郎，然后對(duì)應(yīng)左圖的坐標(biāo)蜗元，就能發(fā)現(xiàn)規(guī)律。其中值得注意的是：k的作用是控制圈數(shù)系冗，同時(shí)精髓就在第二個(gè)for中的第一語(yǔ)句和第二語(yǔ)句奕扣，這兩個(gè)地方做到了特殊點(diǎn)特殊處理！Ｕ凭础）
方法二：類(lèi)似的找規(guī)律惯豆，但是沒(méi)有打表池磁。
#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講的非常詳細(xì)了，在此并不贅述楷兽。其實(shí)思想都是一樣的地熄，不過(guò)我更喜歡方法一。
方法三：建立斜坐標(biāo)系芯杀。
#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 } };//斜坐標(biāo)系的六個(gè)方向
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就可以撤出來(lái)了~
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];//然后向其他剩余的五個(gè)方向各走p步
t--;
if (t == 0) goto L1;
}
}
}
L1: cout << xcord << ' ' << ycord << endl;
}
}
dalao的代碼端考，希望后面有機(jī)會(huì)能夠用自己的語(yǔ)言改一下！挖坑X(jué)1揭厚；
看圖就應(yīng)該明白題意了。
本題的難點(diǎn)在于建圖---輸入一共有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;
}
這是非遞歸建圖的方法太援，其實(shí)很簡(jiǎn)單闽晦。
【
將此蜂巢分成三份，分別是 1...n粉寞，n-1和n交替出現(xiàn)尼荆，n...1。
】
方法二：遞歸唧垦。
此程序個(gè)人化非常嚴(yán)重，就不貼完全代碼了液样。
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);
}
注：這里遞歸建圖的時(shí)候是以列建圖的振亮。個(gè)人認(rèn)為第二段代碼不必用vector，與方法一采用類(lèi)似的寫(xiě)法即可鞭莽，在此再挖一坑坊秸。挖坑X(jué)2；
