2014
03-23

# Hauling Ore

Administrator Selfridge is analyzing possible mining routes on Pandora. He has collected some data in the form of a graph. The latest ore carriers can visit exactly 3 mining camps. Your goal is to help him find out which mines may be visited from other mines with 2 stops (but not fewer).

Connections between mines are described beginning with the line ”GRAPH BEGIN”. Additional lines lists individual mines (nodes), followed (on the same line) by their neighboring mines (edges). The line ”GRAPH END” ends the list of path descriptions. The next lines list mines for which answers need to be calculated, each on a single line. Following these lines, a completely new instance of the problem can be given, starting from scratch.

Some mines may appear only as neighboring mines, without being described on a separate line. Mine names can be arbitrary strings, as long as they don’t contain any whitespace.

Connections between mines are described beginning with the line ”GRAPH BEGIN”. Additional lines lists individual mines (nodes), followed (on the same line) by their neighboring mines (edges). The line ”GRAPH END” ends the list of path descriptions. The next lines list mines for which answers need to be calculated, each on a single line. Following these lines, a completely new instance of the problem can be given, starting from scratch.

Some mines may appear only as neighboring mines, without being described on a separate line. Mine names can be arbitrary strings, as long as they don’t contain any whitespace.

GRAPH BEGIN
a b c
b c d
d e f
GRAPH END
a
b
c
d
e
f

d
e f
d
a c
b f
b e

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
char map[10][10];
int t;
int maxn;
int sum;
int move[8][2] = {1,0,-1,0,0,1,0,-1,1,1,1,-1,-1,1,-1,-1};
bool yescan(int x,int y)
{
if(x < 8 && x >= 0 && y < 8 && y >= 0)
return true;
return false;
}
void DFS(int xx,int yy)
{
for(int i = 0;i < 8;i ++)
{
int flag = 0;
int x = xx + move[i][0];int y = yy + move[i][1];
while(yescan(x,y) == 1)
{
if(map[x][y] == '*')
break ;
if(map[x][y] == 'D')
{
sum += flag;
break ;
}
if(map[x][y] == 'L')
{
flag ++;
x += move[i][0];
y += move[i][1];
}
}
}
return ;
}
int main()
{
scanf("%d",&t);
for(int k = 1;k <= t;k ++)
{
memset(map,0,sizeof(map));
for(int i = 0;i < 8;i ++)
scanf("%s",map[i]);
maxn = 0;
printf("Case %d: ",k);
for(int i = 0;i < 8;i ++)
for(int j = 0;j < 8;j ++)
{
if(map[i][j] == '*')
{
sum = 0;
DFS(i,j);
if(sum > maxn)
maxn = sum;
}
}
printf("%d\n",maxn);
}
return 0;
}

1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

3. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

4. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。