一道 Google 竞赛题的解法
2007-03-15 21:53:07 来源:WEB开发网核心提示: 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、统计所有符合条件的路径总数
- ››Google搜索引擎的奥秘
- ››Google测试搜索结果页面右侧内容更丰富的信息栏
- ››Google Dart精粹:应用构建,快照和隔离体
- ››google的代码审查
- ››google analytics清晰追踪爬虫的爬行信息
- ››Google+中文用户在两千万Google+大军中是少数派
- ››Google AdWords最昂贵点击成本的20种关键词分类
- ››Google运作经理Bryan Power给出的GOOGLE求职意见
- ››Google用户体验的十大设计原则
- ››Google Analytics(分析)能为网站带来什么
- ››Google goggles图片搜索 如何优化一个wap网站
- ››Google Docs将增加iPhone和Android编辑功能
更多精彩
赞助商链接