http://community.topcoder.com/stat?c=problem_statement&pm=10750&rd=14153
http://apps.topcoder.com/wiki/display/tc/SRM+470
因为是棋盘型，然后就想到棋盘型DP；觉得不行，就想到BFS/DFS（这时其实已经把这个看成一张图了）。发现，寻找下一个节点进来的时候，总是要全局考虑所有已经Activate的点，BFS/DFS未果。此时感觉有点像最小生成树的Prim算法，用贪心的，但不知如何证明。此时看了一下题解，发现果然可以规约成最小生成树。因为本质是把棋盘看成一棵树后，整个过程就是Prim的过程。Kruskal的复杂度是O(e*loge)，适合求稀疏的图，Prim的复杂度是O(n*n)，与边无关，适合求稠密的图。（注：Prim使用堆优化效率可更高。）
Prim算法的讲解：http://www.nocow.cn/index.php/Prim%E7%AE%97%E6%B3%95
参考答案的实现也是O(n*n)的，n为w*h。虽然实现方法和纯粹用邻接表表示的有不同（因为具体问题），但效率并无退化。
我在实现错误的将四个方向的组合从(1,0)这样的搞成了(1,-1)。这表示用两个数组，然后循环遍历，也很简洁。其实里面的变量可以命名为row, col等。
int[] r = new int[] {0, 1, 0, -1};
int[] v = new int[] {1, 0, -1, 0};
代码：
import java.math.*;
public class ActivateGame
{
public int findMaxScore(String[] grid)
{
int h = grid.length;
int w = grid[0].length();
boolean[][] activated = new boolean[h][w];
activated[0][0] = true;
int[] r = new int[] {0, 1, 0, -1};
int[] v = new int[] {1, 0, -1, 0};
int sum = 0;
for (int cnt = 1; cnt < h*w; cnt++)
{
int max = 0;
int ar = 0;
int av = 0;
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
{
if (activated[i][j])
{
for (int x = 0; x < 4; x++)
{
if (isValid(i+r[x], j+v[x], h, w) && !activated[i+r[x]][j+v[x]])
{
int score = Math.abs(getScore(grid[i].charAt(j))-
getScore(grid[i+r[x]].charAt(j+v[x])));
if (score > max)
{
max = score;
ar = i+r[x];
av = j+v[x];
}
}
}
}
}
sum += max;
activated[ar][av] = true;
}
return sum;
}
private int getScore(char c)
{
if (c >= '0' && c <= '9')
{
return c - '0';
}
else if (c >= 'a' && c <= 'z')
{
return c - 'a' + 10;
}
else if (c >= 'A' && c <= 'Z')
{
return c - 'A' + 36;
}
return 0;
}
private boolean isValid(int x, int y, int h, int w)
{
return (x >=0 && x< h && y>=0 && y < w);
}
}