一道 Google 竞赛题的解法

核心提示： 2.1判定两位置是否可以彼此移动得到的算法在find每个字符的相应位置向量中，并非每个位置都是有效的(例如例1中，一道 Google 竞赛题的解法(5)，字符A在grid中在两个位置出现，但仅有一个位置可以作为起点)，则将它保存到原来的位置向量中去//否则返回0if ( midVes.si

2.1　判定两位置是否可以彼此移动得到的算法

在find每个字符的相应位置向量中，并非每个位置都是有效的(例如例1中，字符A在grid中在两个位置出现，但仅有一个位置可以作为起点)，所以我们需要判定两位置是否可以彼此移动得到的算法。通过观察两个可以彼此通过向上，向下，向左，向右，以及对角线移动一格移动到达的坐标的特点，我发现符合条件的两个点的位置纵横坐标的差还是有规律的:向上移动的差值为(0,1),向下(0,-1)，向左(1,0)，向右(-1,0)，左上角对角线(1,1),右上角对角线(-1,1),左下角对角线(1,-1),右下角对角线(-1,-1)。归纳这8种情况可以得到这么个结论：两位置纵坐标横坐标差值的绝对值中，有一个必须是1，另一个必须小余2(即0，1两个值),假设两位置纵坐标横坐标差值的绝对值分别是xAbs，yAbs，则( xAbs == 1 && yAbs < 2 ) || ( yAbs == 1 && xAbs < 2 )(显然 这种判定的方法可以排除在相同位置停留两次的情况,此时xAbs和yAbs的值都为0)。 若以用例1为例，其grid中的点E的坐标为(1,1),左上角A的坐标为(0,0)，则xAbs = |1-0| = 1, yAbs=|1-0|=1,符合判定条件，所以E点可以移动到这个A点。而另一个A点坐标为(1,2)则xAbs=0,yAbs=1,符合判定条件，所以E点也可以移动到这个A点。

2.2 判定算法的框架

接下去我们需要将当前位置向量中的每一个值与前一个位置向量中的每一个值逐个比较判定。假定现在判定find中位置为第i个字符与前一个位置向量中点的关系,我们可以这么做：保存find第i字符在grid中位置的向量为vec[i],保存在vec[i]中其第j个位置坐标可以用vec[i][j]取得；由于需要和前一个位置向量(vec[i-1])比较,显然i从1开始,且i< find字符串长度。遍历从位置1开始的位置向量中的所有位置坐标的代码如下：for ( i = 1; i < findStrLen ; i ++)
{
　　for ( j=0; j < vec[i].size(); j++)
　　{
　　　　POS cur = vec[i][j];
　　　　.....计算cur 与前个向量vec[i-1]的结果的代码
　　}
}　　　　　　我添加了一个临时变量VETPOS midVes来保存当前位置向量中符合条件点坐标值。当遍历当前位置中的所有点后，将当前位置向量清空，然后将符合条件并保存在midVes中的位置保存回当前向量中去。如果midVes为空则表示前一个位置向量中的点没有一个可以移动到当前位置向量中的点的位置上去，显然路径已断路，应该马上返回 0。结合前面的代码，得到如下代码：VETPOS midVes;//保存当前位置向量中符合条件点的临时向量
// 遍历从位置1开始的位置向量
for ( i = 1; i < findStrLen ; i ++)
{
　　midVes.clear();
　　
　　//遍历当前位置向量中的所有位置坐标
　　for ( j=0; j < vec[i].size(); j++)
　　{
　　　　POS cur = vec[i][j];
　　　　
　　　　//如果当前点与前个向量vec[i-1]中的点可以移动到达，则保存这个点到临时变量midVes中去
　　　　if (　pathCount(cur,vec[i-1]))
　　　　{
　　　　　　midVes.push_back(cur);
　　　　}
　　}
　　//清空原来的向量
　　vec[i].clear();
　　
　　//如果midVes中有符合条件的点存在，则将它保存到原来的位置向量中去
　　//否则返回0
　　if ( midVes.size() >0 )
　　{
　　　　vec[i] = midVes;
　　}
　　else
　　{
　　　　return 0;
　　}
}　　　　　　代码中的 pathCount(cur,vec[i-1]) 用来计算cur点与前一个位置向量vec[i-1]的中的点存在可能的路径数，如果返回0则表示点cur无法按照题意移动到保存在前一个位置向量vec[i-1]中的任何一点。pathCount的实现将在下文描述。