一道 Google 竞赛题的解法

核心提示： 2.3统计每个位置向量中每个位置的当前符合要求的路径数如果将所有的符合find字符串的路径全部找到，然后再统计总数的话，一道 Google 竞赛题的解法(6)，就需要多次遍历vec向量，由于题目并没要求我们将符合的路径输出，pre表示前一个位置向量，返回值为通过ps点的可能路径数，所以完全

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点的可能路径数。函数实现代码如下：

int pathCount(POS &ps, VETPOS& pre)
{
　　//初始为0
　　ps.count = 0;
　　int i;
　　
　　//遍历pre中的每个位置坐标
　　for ( i=0; i < pre.size(); i++)
　　{
　　　　//计算cur与pre[i]的纵横坐标差的绝对值
　　　　int xAbs = ps.x - pre[i].x;
　　　　int yAbs = ps.y - pre[i].y;
　　　　
　　　　xAbs = xAbs < 0?-xAbs:xAbs;
　　　　yAbs = yAbs < 0?-yAbs:yAbs;
　　　
　　　　//判断是否可以移动到达
　　　　if (( xAbs == 1 && yAbs < 2 ) ||
　　　　　　( yAbs == 1 && xAbs < 2 ) )
　　　　{
　　　　　　ps.count += pre[i].count;//统计通过ps点的可能路径数。
　　　　}
　　}
　　
　　return ps.count;
}　　　　3、统计所有符合条件的路径总数