Stoer-Wagner算法

Stoer-Wagner算法是用来计算无向图的全局最小割的，理论上复杂度可以为O(|E|+|V|log|V|)。我的实现不是最好的，但觉得还行吧。

网友的好文章：最小割Stoer-Wagner算法

题目是百度06年的复赛题，星球大战。可以在POJ上练习，POJ2914。

相关论文和偶的代码，可点此下载。

Stoer-Wagner算法的实现：

#include  <iostream>
#include <algorithm>
using namespace std;

#define initSet(n,Arr) for(int i=0;i<n;++i)Arr[i]=i;
#define MAX 1<<30;
int graph[600][600];

// Stoer-Wagner Algorithm
int globalMinCut(int n){
// A is A set for Stoer-Wagner Algorithm
bool* A=new bool[n];
// V is vertex index
int* V=new int[n];
int* W=new int[n];

initSet(n,V);

int best=MAX;
while(n>1){

//the most tightly connected vertex.
int maxj=1;

// initialize set A and other vertex's weight
A[V[0]] = true;
for(int i=1; i<n; ++i){
 A[V[i]]=false;
 W[i]=graph[V[0]][V[i]];

 if(W[i]>W[maxj])
  maxj=i;
}

// find a min-cut
int prev=0,buf=n;
while(--buf){
 // add it to A
 A[V[maxj]]=true;

 if(buf==1){
  // update min cut
  best=min(best,W[maxj]);

  // merge prev and last vertex
  for(int k=0; k<n; ++k)
   graph[V[k]][V[prev]]=(graph[V[prev]][V[k]]
     +=graph[V[maxj]][V[k]]);
  V[maxj]=V[--n];  
 }
 prev=maxj; 
 maxj=-1;

 // update the weights
 for(int j=1; j<n; ++j)
  if(!A[V[j]]){
   W[j]+=graph[V[prev]][V[j]];
 
   if(maxj<0 || W[j]>W[maxj])
    maxj=j;
  }
}
}

delete[] A;
delete[] V;
delete[] W;
return best;
}


int main(){
// n - vertex number
// m - edge number
int n,m;

while(scanf("%d %d",&n,&m)==2){
memset(graph,0,sizeof(graph)/sizeof(bool));

// v-w is an edge with c weight
int v,w,c;

while(m--){
 scanf("%d %d %d",&v,&w,&c);
 graph[v][w]+=c;
 graph[w][v]+=c;
}

// output min cut
printf("%d\n",globalMinCut(n));
}
}

百度之星2007初赛

HOHO，恭喜恭喜，上大的四人都过初赛啦！ 我，梁老大，沈还有Jackie Yu。我和Jackie两天都做了，沈做了第一天，梁做了第二天。最后沈和梁晋级，我靠第一天晋级，Jackie靠第二天晋级。我第一天拿了30分（题1全过，题2过一半），比期望的低哦，最后的那道SQL本来希望能过两个CASE的，结果全挂了，555，沈也是用暴力解的，但他过了两个CASE，估计是我哪里细节出了问题，导致全错。第二天很郁闷，中午做题果然没晚上精神爽，直打瞌睡。第二天只做了两道（1，4），最后的结果是第1题只对了一个case， -_-b，超级郁闷，后来发现程序里少了两句判断，555，不然第二天也能晋级啦，现在只有9分，不过还好有第一天保底（只是对不住陈胖子了呀）。

题目可以见某网友的帖子，感谢他保留了百度试题：
http://www.ninstein.com/blog/article.asp?id=199
http://www.ninstein.com/blog/article.asp?id=202

其他的题目就不说了，百度有点评（第二天要准备trie的模板呀），我个人对第一天的第四题SQL的SELECT语句比较感兴趣，所以重新做了一遍：

基本上是做了两点的优化（较暴力法），一个是结构上加了索引，二是计算满足条件的几个集合的交集（在结构的基础上优化的求交算法）。

为了说明结构我画了图，还不错吧 ^_^

简单说明一下，该结构完全是为了针对题目而做的，我考虑下，为了实现Delete, Update还需要修正一下结构，而且结构改动后后面的Select算法也要调整。另外，Select是单向的，即只能由条件找出记录号，不能由记录号找出记录的所有信息，要实现的话应该在Record上再加一些变量。不管了，只是针对AND逻辑的嘛。

Table[i][j]的位置不是存放第 i 记录的第 j 字段值，而是存放一个指针，指向下一个与Table[i][j]值相同的记录号，也就是链表结构。索引表存放的才是字段值，对应一个startId是在Table中的第一个拥有该字段值的记录号，即链表的head。

假设，按图中sample有5条记录，0 1 3的c3字段值为a，2 4的c3为b。那么Select c3为a的所有记录，就是在IndexTable中找c3的字段索引，然后找对应的a的startid，得0。然后回表中开始找出所有记录，Table[0][c3]=1, Table[1][c3]=3, Table[3][c3]=-1。-1为终止，于是有 0 1 3 三条记录。

由上可以求出，满足某字段值的一个集合。第二步是求满足多个字段值的一个交集。由于结构本身提供了一个很有利的条件，即若Table[i][j]的字段值等于Table[i][k]且两者均不为-1，则Table[i][j]<table[i][k]当且仅当 j<k，算法描述如下：

（假设满足求n个condition的记录数count=0）
if condition is empty
count=recordNum, exit

准备一个索引数组tb，tb[i]代表 i 条件下的当前记录号。tb初始全-2。
foreach condition as ci
int tmp= IndexTable中ci条件的startid值，无法满足ci，则tmp=-1
if tb[ci] 已存在，即 !=-2
 if tb[ci]!= tmp
     count=0, exit
  else
      next condition
else
  tb[ci]=tmp

依某算法（算法很多，自定吧）取字段c为主键，可以理解为取某个condition为主条件

while tb[c]!=-1
foreach condition as ci
if ci==c
    continue
else
    while tb[ci]<tb[c] && tb[ci]>=0
     tb[ci] = Table[tb[ci]][ci] // next record
    if tb[ci]>tb[c] || tb[ci]==-1
        break;
if all condition matched
count++
else
tb[c]=Table[tb[c]][c]

count is result

复杂度分析： 空间复杂度上是不会亏的啦，字段值没有重复保存过，索引用的都是数字。设记录数n，字段数c，构造DB时的复杂度O(nc)。设某个查询的条件是q条，查询的复杂度min(q,c)+sum(count(qi)) min(q,c)是条件数和字段数取小者，qi表示第i个条件，count是满足i条件的记录数（可以缓存一下的），sum()为求和函数。

其他建议：取主键的算法很多（甚至可以不取，直接假设第一个条件对应的键为主键），可以单纯地用缓存过的满足条件的记录数来决定记录数最少的那个为主键。但对于复杂度不会有提高，因为如果按我上述的算法，复杂度是固定的，主键不影响复杂度。

存在不同主键的情况下会影响复杂度的算法，假设已经求到Table[i]是满足所有条件的记录，那么求下max(Table[i][cj]) cj为每个条件对应的字段，只有最大值对应的记录才有可能为下一条满足所有条件的记录，即使他不是满足所需要的记录，那么只要循着该字段一定能找到真正的下一条满足所有条件的记录。这种跳跃式的算法，可以有效减小复杂度。

缺点：结构只是针对select and做了优化，并没考虑太多，可能会不方便其他操作。优化中将记录标号了，虽然现在大部分表都喜欢加个id，但数据库本意是记录无序的。如我图中所画，DB有许多Table，而只有一个IndexTable，我的想法是一个IndexTable可以管理所有有关联的Table的所有字段，以优化做select and操作。但还没设计完，现在的IndexTable显然是不行的，以后有机会再说吧。

偶的代码（C++），大致实现了上面的结构和算法，测试数据使用MySQL 的sakila sample 的payment表，修正后的数据以及代码点此下载 (放在上大ACM论坛，-_-b荒废好久的论坛啊，只能用来摆摆文件了)：

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <utility>
#include <sstream>
#include <algorithm>
using namespace std;

// DB structs
// first is startId, second is len(len may be tempory used for other target)
typedef pair<int,int> Index;
typedef map<string,Index> FieldIndex;
typedef vector<FieldIndex> IndexTable;
typedef map<string,int> ColumnName;
typedef vector<int> Record;

struct DB{

// a table (since only one table provided)
string name;
vector<Record> records;
int recordNum,columnNum;
ColumnName nameMap;

IndexTable it;

DB(int n,int c):recordNum(n),columnNum(c){
 records.resize(n);
 it.resize(c);
 for(int i=0;i<n;++i){
  records[i].resize(c);
 }
}
};

// Query structs
typedef pair<string,string> Expression;
typedef vector<Expression> Query;

// called while constructing the DB and IndexTable
int addValue(FieldIndex& index, string& value,int curIndex){
map<string,Index>::iterator iter=index.find(value);
int lastIndex=-1;

if(iter==index.end()){
 index[value]=Index(curIndex,curIndex);
}else{
 lastIndex=index[value].second;
 index[value].second=curIndex;
}

return lastIndex;
}

void initDB(DB& db){
string buf;
// parse db name
cin>>db.name;
getline(cin,buf);

// parse column name
getline(cin,buf);
stringstream ss(buf);
string name;
for(int i=0;i<db.columnNum;++i){
 ss>>name;
 db.nameMap[name]=i;
}

// parse db records
for(int i=0;i<db.recordNum;++i){
 getline(cin,buf);
 stringstream ss(buf);

 for(int j=0;j<db.columnNum;++j){
  string value;
  ss>>value;
  db.records[i][j]=-1;
  int lastId=addValue(db.it[j],value,i);
  if(lastId>=0){
   db.records[lastId][j]=i;   
  }
 }
}
}

bool isExpression(string& str){
int len=str.length();
for(int i=0;i<len;++i){
 if(str[i]=='=')return true;
}
return false;
}

bool validChar(char c){
return (c>='0' && c<='9') || (c>='a' && c<='z') || (c>='A' && c<='Z');
}

void parseExpression(string& str, Expression& exp){
int i=0,st=0,len=0;

while(!validChar(str[i]))++i;
st=i;
while(validChar(str[i]))++i;
len=i-st;

exp.first=str.substr(st,len);

while(!validChar(str[i]))++i;
st=i;
while(validChar(str[i]))++i;
len=i-st;

exp.second=str.substr(st,len);
}

int doQuery(DB& db,string& q){
int cnt=0;
stringstream ss(q);
string buf;
Query query;

while(ss>>buf){
 if(isExpression(buf)){
  Expression exp;
  parseExpression(buf,exp);
  query.push_back(exp);
 }
}

if(query.empty())return db.recordNum;

int* tb=new int[db.columnNum];
fill(tb,tb+db.columnNum,-2);
 
for(Query::iterator iter=query.begin(); iter!=query.end(); ++iter){
 int col=db.nameMap[iter->first];
 map<string,Index>::iterator mapIter=db.it[col].find(iter->second);
 if(mapIter!=db.it[col].end()){
  int st=(mapIter->second).first;
  if(tb[col]>=0 && st!=tb[col]){
   return 0;
  }else if(tb[col]<0){
   tb[col]=st;
  }
 }else tb[col]=-1;
}

int lastValue=-1;
while(true){
 int i=0,curValue=-1;
 for(;i<db.columnNum;++i){
  if(tb[i]==-2)continue;
  if(lastValue>=0 && tb[i]==lastValue){
   tb[i]=db.records[tb[i]][i];
  }  
  if(tb[i]==-1)break;  
 
  if(curValue==-1){
   curValue=tb[i];
  }else{   
   while(tb[i]<curValue && tb[i]>=0){
    tb[i]=db.records[tb[i]][i];    
   }
  
   if(tb[i]>curValue || tb[i]<0){
    break;
   }
  }
 }
 lastValue=curValue;
 if(tb[i]==-1 || curValue==-1)break;
 if(i==db.columnNum){
  ++cnt;
 } 
}

delete[] tb;
return cnt;
}

// main entry
int main(){
int c,n,q;
cin>>c>>n>>q;
DB db(n,c);
initDB(db);

string line;
while(q--){
 getline(cin,line);
 cout<<doQuery(db,line)<<endl;
}
}

07年5月29日 在复旦大学的topcoder比赛

先是匹萨，棒约翰的，还不错，我和肖各吃了两块，就饱了，其实是不太好意思吃多 ^_^

然后是比赛，感觉脑子的转速要比在家里做快得多，时间也貌似比一般的一个半小时长得多（因为单位时间的思考能力强了，所以感觉时间就多了）。算是三校联赛吧，被复旦踩是必然的，目标是踩东华。最后338.31，是room2的第7，divsion的第13，还是被两个东华的踩了。

很久没写tc报告了，因为很久不关心算法。但今天还是满有意思的，写一下，纪念一下：

总得来说DIV2的题目就是比较简单的呀。

problem 250:
一个Set包括0-9个数字，其中6和9可以互用，隐含的意思就是可以表示 66 或 99 或 69。
然后给个门牌号，问至少买多少Set能够摆出这个门牌号。

算法很简单，统计一下门牌号中出现过的数字个数。因为6和9可以互用，所以把6的个数和9的个数平均一下，有两个写法：

// method one, after counting
count[6]=count[9]=(count[6]+count[9]+1)/2;  // forget add one will be chanllenged

// method two, in counting iteration
if(count[6]<count[9]) count[6]++;
else count[9]++;

看到两个人用第一种写法忘记+1，cha之~，HOHO，赚100分。

problem 500:
有金G银S铜B三种钱币，去银行转换的规则如下：
11 S -> 1 G
11 B -> 1 S
1 G -> 9 S
1 S -> 9 B
问从G1 S1 B1换到 G2 S2 B2的最少交换次数，或-1表示不可能

与其说是贪心，不如说是逻辑题，只要依存简单的逻辑，就能既保证代码清晰，又可保证准确率：
step 1. 如果B不够，只能用S换B
step 2. 如果G不够，只能用S换G
step 3. B和G都够了，若S不够，先用G换S，再用B换S。因为G换S一次可以满足的S多，所以先G换S。

5555，前面的代码都是好好的，可惜最后在B换S的地方，忘记减去B，加上S了。。。好粗心啊 >.<
一开始沈发现了，但他给的cha数据没能把我cha掉~，洋洋得意地笑沈时，忽然某人把我cha了~ 瞬间郁闷

problem 1000:
比赛的时候想了n套方案，结果还是没能决定用什么方法解之。
题目意思是给出一个序列，要求用最小的cost排序，将i放到某个值后面/前面，花费的cost是i。

大大的程序千奇百怪，有STL库牛人的，有搜索解的，有DP的，不过最欣赏的是这个解法：
可以把问题转换为， 求顺序的最大cost的序列，然后用总cost减一下就行了。

例如sample 中的 6 4 5 3 8 2 7 2 11 2 2，顺序序列可以是 4 5 8 11，也可以是4 5 7 11，对于一个顺序序列，剩余的部分便是待移动的数，为了保证待移动的数的cost尽可能小，就是保证顺序序列的cost尽可能大，所以取 4 5 8 11 的cost和为28，所以只需要用最少52-28=24来完成排序。按照这个思路，有程序：

public int calcMinimalCost(int[] arr){
int total=0,len=arr.length,maxCost=0;
int[] cost=new int[len];

for(int i=0;i<len;++i){
  cost[i]=arr[i];  
  total+=arr[i];

  for(int j=0;j<i;++j){
    if(arr[j]<=arr[i] && cost[j]+arr[i]>cost[i]){
       cost[i]=cost[j]+arr[i];
    }
  }
  maxCost=Math.max(cost[i],maxCost);
}

return total-maxCost;
}

TCO Marathon Online Round #2

TCO Marathon OR2 finished. I got 65/445 rank, 11331.73 score, and advance to round 3 successfully. My friend, FinalLaugh, got rank 191, while he has got 200 rank when the submission parse finished, just by a finger's breadth. The path to Las Vegas is becoming more and more narrow, next time , we will fight for 50 contestants position.

The top 2 players' program scares me a lot...... So many codes that looks like "AA>s;oI2A". As we, FinalLaugh and I, discussed, it's a technology of compress.

I dislike this problem, two reasons: 1st, it's a gambling game; 2nd, it's solution is not so hard, but with a lot of work. My solution is so easy to implement ， somewhat like saarixx (rank 7) did.

First of all, list all card combinations: {4,4} {3,3} ... 15 cases from high to low. Then, provide a simple solution to newcard(), round1(), draw() then take them into an array, each owns 15 elements, just like this:

 private int[] newc = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0 };
 private int[] rd1 = { 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0 };
 private int[] draw = { 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2 };

For these three method, I think, a fixed strategy will be ok. As to round2(), it's more complexity, but as I'm so lazy.... I realize it like this:

   public int round2(int card1, int card2, int bets1, int bets2, int drew) {
       int idx = getCardIdx(card1, card2);

       // pre solution, like the too little card will return 0 immediately
     
       switch (drew) {
       case 2:
           // some solution
       case 1:
           // some solution
       case 0:
           // some solution           
       }
       return -1;
   }

That's all, so simple but strong enough to advance to the next round. Wish my good luck next round!

TCO Marathon Online Round #1

TCO Marathon OR1 and OR2 has finished today, which consume my thoughts for two weeks.

To OR1, I got 1309.01 at submission phase and 4990.66 at end, final rank 67/532. See the problem here(need login), which is a really interesting and challenge game. As my solution, the image could be considered as a onion, the target of this prob is to peel the onionskin. So, here is the steps of my algorithm:

1. Generate the rays, those rays will be the easy calculating ones. (Attention, generate rays does not mean call the measure() method.)
2. Pick out the rays that just cross one unit('x' unit), and store them in a queue.
3 Iterate the selected rays, calculate the density of that unit(call measure() here), and then mark the unit as calculated.
4 Repeat step 2, but the more repetition we used, the more precision we will lost. It should be a bound to control the precision before we start this algorithm.

As to step one, the rays should be selected meet the condition that they will be easy to calculate, otherwise, it will be a great amount work of calculation and simulation. As I considered, each ray will start from one of the four corners of the unit, and the ray should cross exactly n row unit while it crossed 1 col unit, and vice versa. The main reason I ensure this condition is that every length of the row unit( according to my example) that the ray would cross is the same, and that would lower the complexity of the ray calculation. As a result, when n is greater than 30(I forget the exactly number, but 30 is enough), every unit will be covered.

As to step four, the repetition times is a hard decision. The performs of different repetition times would result in a normal distribution, and the peak of the distribution is the one we desired. I choose the repetition according to a great amount of test.

Topcoder Marathon 11

Marathon的System Test也是Marathon式的，等了好久。

最后的Rank终于出来了，Rank 8, Score 388.10, Rating 1565。
第一名好夸张，有好多Case都是超我一倍的呀！赞~

第一次做Marathon，这次的题目是贪吃蛇，郁闷...是比较没新意的题目...个人感觉贪吃蛇运气因素较大（测试数据多的话，当然可以降低偶然性），没有觉得能在每盘上都赢得最高分的算法，但确实应该有能保证在大多数情况下表现出色的算法。
我的算法可以说是偶然性十足 -_-b，我也很纳闷，但就是没法解释，所以只能说偶然。Example Test 15次，Submittion 4次， Submittion的成绩是 30.76 -> 28.44 -> 28.13 -> 27.43 一个比一个差 -_-b （但我的想法好象是一个比一个周密才对呀）。

我的算法的思路是这样的：

Step 1. 将Snake的一次行为（调用 moveSnake()）划分为三个小算法， 即计算路径、选路径、移动。

Step 2. 初始化地图我不算在算法里，因为太简单了。计算路径是指，用搜索类的算法，搜索出从Snake到Food的可能路径。

在这一步，我起初使用的是最简单的bfs（就是我得分最高的时候 -_-b）。优点是找到的豆路径最短，缺点是Snake老是擦豆而过，因为路径只关心最短的问题，如果路径上没有经过某个豆，那么即使该豆可以顺便吃掉，Snake也会置之不理。
然后，我改进了算法，使用pfs，以吃到的豆的个数为优先级别进行路径搜索。这样每次都是从吃豆最多的路径继续往下搜，就可以保证将顺路的豆子都能吃掉。结果是，这个pfs每次比bfs走的步数要少，从虚拟程序上看，Snake聪明了许多，但就是吃豆数不见长。

我这有一个我没去实现的算法（因为后面两天都有事），想法是使用多端bfs：Snake头和各个Food各准备一个队列，然后每个循环，依次对每个队列进行扩展。当某个Food队列扩展的路径碰到了Snake的路径，那么Snake到该Food有路；若是Food队列碰到Food队列，那么这两个Food有路。且所有路径最短。改算法的好处是能求出所有最短路径、而复杂度与bfs相同，只是实现有点复杂。

Step 3.选路径，在我自己测试的时候发觉，选路径对于整体结果影响最大！也可以说是偶然性最大的一块。依据Step2中的bfs或者pfs所得到的结果，应该说Snake到Food的路径是固定的，所以就可以说是选下一个受吃的Food。怎么选Food呢？
我给每个Food设置了三个值：

1. 吃到该Food的路径上顺便可以吃到的Food
2. 假设Snake吃该Food，那么吃到Food后，Snake的可移动空间，即一次bfs从Food点开始计算空间（要先模拟好Snake吃到Food的位置）。
3. 该区域内还有多少未吃的Food，即如果Snake逃不出该Area，可能还有多少Food可以吃。

综合上述三点，可以计算出一个优先级。我以Area大小和Snake蛇身长度为主要依据，若蛇身长远远超过Area那么Snake应该说可以有更大的活动，也可以说Snake有机会逃出该Area。再依据Snake吃该Food时顺便吃的Food和该Area潜在的Food同样影响这个优先度。若优先度相似，则可能再吃的Food数量加上顺便吃的Food数量为第二优先级。
在这里，Area的关系十分重要，很明显的，因为Area表示Snake存活概率高，只要活着就不怕没Food吃。
比如下面两个情况：

 #                   ###
#O                  #  #
 #                   #O#

很明显，这些Food是DeathFood，优先级要最低，也就是说实在没Food可吃才吃他们。

对于多端bfs，选择的就不是Food了，而是真正的Path。这个就可能和前面的算法完全不同了，我又没实现多端bfs，而且这个貌似更加复杂，就没深入。。。另一方面是被偶然性搞怕了，深怕花了大半天写的程序结果还不如以前的好。

Step 4.移动，即与平台交互，这个只要认真看看平台文档就行了。另外，为了保持Snake和Food位置与平台同步，自己也要模拟Snake的移动。

附加一个想法，由于Step3提到，Snake吃到Food后的Area问题。所以我考虑是否可以通过预广搜一次，标记所有的Area（或者这里称Prison，也就是整个Area有一个格子负责与外界连着，其他格子均与非此Area的格子无连接）。起算法是，由任意一点，开始bfs，但搜索到的格子只有一个目（类似于围棋的目，就是下面这种情况，X是搜索过的格子，#是障碍物，@就是只有一个目）：

XX#
XX@
XX#

这种情况下，将@放入一个Door队列（初始为空）。若搜索第二次遇到@，则@不是Door，标记为搜索过的格子。在待搜索队列为空时，若Door个数大于1，则Area不是Prison，可以再扩展；否则该Area为Prison，同时去除该Door。然后任取一个外面一个没有搜索过的格子再bfs，同样，若搜索到某个Door则取消它Door的资格，否则搜索完再计算Door个数。
可能出现这种情况： Prison - Door - 2个Door的Area - Door ，此时，2个Door的Area不是Prison，但它加上里面的Door和Prison就是一个Prison。可以说是有层次关系的。
总之，算法很复杂，当时摆着电脑楞了许久，最后还是决定先暂时把这个想法搁着 -_-b 。

蜜蜂的问题

老blog里比较不舍得丢的文章，移到这里来：

99年ACM/ICPC 的final有一道蜜蜂的坐标的问题，非常有意思，和队友们讨论了许久都没能解决。记得那天做练习是我和肖筹划着用计算几何的方法估算出结果，虽然做法很独特，但毕竟是估算的，最后没有能过。后来我找了份解题报告，看到了解这类问题神奇地使用笛卡儿坐标，着实让人兴奋啊。所以准备了一份模板、数道类似问题和将蜜蜂坐标放在扫雷游戏里的应用，来一个蜜蜂问题的大汇总。

模板放在SHU ACM群里，含有一些处理正六边形拼成的坐标系的方法。

首先，蜂巢是由许多个正六边行无缝拼接而成的，这是一个美丽而奇特的自然结构，如图（图中程序是在解一道题时写的辅助程序，我也放在群与大家分享）：

题外话，先来讨论下为什么六边形可以无缝的拼接出一个平面，那么七边、八边行不行？其实是一个简单的小学题： 正n边形内角为 (n-2)*180/n ，要保证可以无缝拼接，就是一个圆可以被整数个n边形内角拼接，即 360=k*(n-2)*180/n => 2n=k(n-2)，用这个公式就能算一下是否正n边形能像六边行一样拼出一个平面了。

起初在遇到这样独特的结构时可能无法想象如何将其保存起来，可能会想到是不是做一个带六条链结点的链图？这样做的结果将是一个极难维护的链图，光是想到插入操作就起鸡皮疙瘩。

有一个十分巧妙的方法来储存这个怪异的结构：用二维数组。用二维数组保存四个方向或八个方向的东西肯定是很简单的，其实对于这个六向的结构，我们可以取二维数组的八向中的六向。即东、南、西、北、东北、西南（其实只要注意对称，六向可以随便取），这样相对的坐标向每个方向移动的偏移量就是：

东 南 西 北 东北 西南
x 1 0 -1 0 1 -1
y 0 -1 0 1 1 -1

到底正确与否呢，其实是必然正确的，只是我们损失了两个角（东南、西北），不过不碍事。通过上面这个方法不仅是保存了六边形的怪结构，而且也给这种结构指明了一个坐标表示的方法，在解题中这个概念很重要。

PKU 1134：

与蜜蜂坐标没关系的题目，只是样子是六边行的。题目意思是给出三行，每行代表一个方向，然后可以按任意顺序把数字放在这个方向的任意一列中（以abcba的顺序分配到abc里）。归纳一下可以得到以下结论， 最大的得分就是三行分别乘以下面的系数：

行1： a * 8 + b * 6 + c * 5
行2： a * 7 + b * 7 + c * 5
行3： a * 7 + b * 7 + c * 5 。所以枚举一下就可以求出最大值了。

PKU 2265：

这是非常简单、易上手的题目，熟悉两种坐标系对于解决蜜蜂问题很有帮助，这两个坐标系也是蜜蜂最常用的坐标，转换的方法就是直接上模板。

PKU 1870：

是99年FINAL的题目，除了用模板里的构造点来构造一个六边形结点（带XY轴坐标）以外，模板里有求两点间最短距离的函数。

求最短距离要以一点为原点，即用一点减去另一点的XY坐标。然后对相对的那个点的两种情况做处理：xy同正同负时，距离是max(|x|,|y|)；否则距离为距离是|x-y|。简单得想象一下就知道了。

PKU 1792：

是1870的升级版，除了要求最短的距离外，还需要求两个点间有多少种路径可以用最短的距离。其实求可能的路径数可以归约为求组合数的问题：

上图为例，在x>0 y>0的区域，最短距离是max(|x|,|y|),图中某点的最短距离很明显是 |x|，然后如何求路径数呢？这样思考，为了能到达那个点，所有路径在两点之间准没错吧（出了两点间的区域就不能最短距离了）。那在最短路径为d的情况下，取d中的一点让它或上或下（只要保证还在两点间的那块区域），不就可以得到一条新的路径？这样，在d中取c个点（c为最大的可变的点，或称关节），就是总路径数。那么总的路径数就是combine(d,c)了。巧合的是c的值情况与最短路径的值情况正好相反，即xy同正同负时，c为|x-y|；否则c为max(|x|,|y|)。

模板里有个函数实现此功能，不过自己写写也很简单的吧。

PKU 3036：

哈，在1792有点类似，不过做法完全不一样的题。求的是从原点出发到达距离为n的地方再回来的路径数。其实知道用动态规划和前面讲的六个方向的坐标的话，这道题目是非常简单的。动规方程见下：

dp[i][x][y] i表示距离原点i步；xy是点的坐标。

 dp[i][x][y]=  dp[i-1][x+1][y] + dp[i-1][x-1][y] + dp[i-1][x][y+1] +dp[i-1][x][y-1] + dp[i-1][x-1][y-1] + dp[i-1][x+1][y+1]

初始dp[0][x][y]都为0，dp[0]原点为1。然后开始dp，最后dp[i]原点就是第i步的解。

上面的是比较简单的或基于六向的坐标系的，下面两道比较有意思，是对于此类坐标系的扩充：

PKU 1957：

那个辅助程序就是我为了做这道题目而写的，用法是先输入walk，然后按lrotate可左转（正规化过）。

题目的解法很容易想到的，就是先将走过的点放在一个set里，然后做旋转和正规化，直到两个set的元素都相等为止。

依照行走的路线构造点不是件难事，从原点出发。旋转是比较费神的，正规化的话其实就是找出一个最左最右的点作为参照点，所有点减掉它就行了。

旋转可以从两个角度考虑，一是考虑求出了点之后做旋转，二是考虑在将行走路线做旋转然后求点。如果从前种方向考虑的话，会很累，在简单的四向的坐标系中点相对于原点的转动可以通过乘以一个变换矩阵得到，而对于一个六向的坐标系，举个例子：

一个二维数组保存的七个点（O表示该位置无值，X表示该位置是一个六边形结点）：

O X X               X X O
X X X ===========>  X X X
X X O 乘以变换矩阵     O X X

很明显，旋转后的不是原来使用的六向的坐标表示方法了。当然，调整变换矩阵的话，相信还是有办法解决的，但这毕竟是个较麻烦的活儿。

那么从后者的方向来考虑的话，事情就简单了很多。见下图：

按行走路线进行转换的思想就是上图所表现的，显而易见了吧。代码实现也是相当的简单。即将把原来的a方向的操作改为b方向操作等等。

这样的话，先输入第一种走法，正规化一下。然后输入第二种，做七次旋转（包括不转的那种），每次正规化后再比对两个集合就行了。

PKU 1518：

看上去很吓人的题目，跟计算几何又有关系，而且坐标系又是要六向的表示。Take it easy，先来看看一个扫雷游戏吧：

在扫雷游戏中有这样一个问题，鼠标点击了之后要出发事件，事件的参数只有鼠标点击的点的坐标(x,y)。求鼠标点击的是哪块雷区，知道了哪块雷区才可以做相应操作嘛。

通过平面坐标求六边形的坐标的方法其实满多的，在这里介绍一个简单的方法：

首先，要判断点是否在六边形内，经常使用的是用叉乘判断点对于凸边形的每个顶点是左转还是右转可以做到。不过这里不需要这么做，因为六边行都是紧凑得在一起，而且都是正多边形，所以求一下点到每个多边形中心的距离，然后取最小值可以找到它所在的六边形了（如果正好在边上，随便取哪个都一样）。

为了优化一点，不用对每个六边形都求一下它的中心与目标点的距离。可以先从距离估算出目标点的大致位置，然后包括大致位置的六边形在内，相邻的六个六边形再确定出最终点所在的六边形。

估算的方法是简单的计算几何（d是六边形边长，td是sqrt(3)*d/2，p是目标点）：

x = (int) Math.round((p.x * 2 / (3 * d)));
y = (int) Math.round(((-p.y + x * td) / (2 * td)));

知道了六边行的坐标，接下来的事情就容易了。求两坐标间最短路径，然后路径乘以2*td。再将具体的两个点与六边形中心的距离相加。就是结果了，当然要注意在同一个六边形内的两点是直接计算两点距离。

链接：

Ray's Blog: http://raythking.blogspot.com/
SHU-ACM-Group: http://groups-beta.google.com/group/shu-acm-group
Mineray: https://mineray.dev.java.net/