![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
在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的实现将在下文描述。
2.3 统计每个位置向量中每个位置的当前符合要求的路径数
如果将所有的符合find字符串的路径全部找到，然后再统计总数的话，就需要多次遍历vec向量。由于题目并没要求我们将符合的路径输出，所以完全可以在寻找路径的同时，也开始统计每个位置向量中每个位置的当前符合要求的路径数。出于此目的，我在POS结构体中增加了int count;这个字段。如例1中,find的第2个字符B，从第一个字符A移动到B的路径只有一条，所以假设POS b，表示这个位置的B点坐标，则ps.x=1,ps.y=0,ps.count=1。显然每个位置坐标的count值，应该为前一个位置向量中的所有可以移动到这个点的count值的和。而第一个位置向量中的每个坐标的count值等于1。即保存在vec[0]中的每个位置坐标的count值设置为1。 我增加了一个函数来处理一个点与保存在前一个位置向量中的每个点是否可以移动得到，并统计通过这个点的可能的路径数。该函数即前面提到的pathCount，其原型如下：
int pathCount(POS &ps, VETPOS& pre)
ps表示当前位置向量中的一个点，pre表示前一个位置向量，返回值为通过ps点的可能路径数。函数实现代码如下：
上一篇:新时代的门前 32位世界中的64位编程
下一篇:Windows Workflow Foundation之概述
|
精品推荐