[topcoder]ActivateGame

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);
	}
}