一道 Google 竞赛题的解法

核心提示： 经过上述代码的运算，保存在最后的位置向量中的每一个点的count字段代表了这个点为终点的所有符合条件的路径数，一道 Google 竞赛题的解法(7)，我们只要将这些点的count值累加就可以得到find字符串在grid中符合条件的路径总数，当然累加时发现这个值已经大于1,000,000,0

经过上述代码的运算，保存在最后的位置向量中的每一个点的count字段代表了这个点为终点的所有符合条件的路径数，我们只要将这些点的count值累加就可以得到find字符串在grid中符合条件的路径总数。当然累加时发现这个值已经大于1,000,000,000,时 就可以马上返回-1了。代码见后面的汇总代码。

4、最后将这个类的实现代码汇总如下：#include < string>
#include < vector>
#include < iostream>
#include < stdio.h>
using namespace std; //Required for TopCoder gcc compiler
//****************************************************************
//类名：WordPath
//作者：roc（txqc4@sohu.com）
//日期：2005-12-13
//用途: 本代码为实现上述竞赛题所作。
//注意事项：如欲转载，请保持本段说明。
//****************************************************************
class WordPath
{
　　typedef struct POINTtag{
　　　　int x;
　　　　int y;
　　　　int count;
　　}POS;
　　typedef vector< POS> VETPOS;
　　
public:
　　
　　int countPaths(vector < string> grid, string find)
　　{
　　　　int findStrLen = find.length();
　　　　int gridSize　 = grid.size();
　　　　int gridStrLen = grid[0].length();
　　　　
　　　　vector < VETPOS> vec(findStrLen);
　　　　
　　　　int i,j,k;
　　　　
　　　　// 遍历grid中的每一个字符
　　　　for ( i = 0; i < gridSize; i ++)
　　　　{
　　　　　　for ( j= 0; j < gridStrLen; j++)
　　　　　　{
　　　　　　　　for ( k=0; k< findStrLen; k++)
　　　　　　　　{
　　　　　　　　　　char ch =　find.at(k);
　　　　　　　　　　//如果与find中位置k的字符相等，则将相应的grid中的位置坐标保存到相应的向量中去
　　　　　　　　　　if ( ch == grid[i].at(j) )
　　　　　　　　　　{
　　　　　　　　　　　　POS ps;
　　　　　　　　　　　　ps.x =j;
　　　　　　　　　　　　ps.y = i;
　　　　　　　　　　　　
　　　　　　　　　　　　//位置向量0中所有坐标的初始值为1，而其他位置向量中坐标的这个字段总会被指零后才计算
　　　　　　　　　　　　ps.count = 1;
　　　　　　　　　　　　vec[k].push_back(ps);
　　　　　　　　　　}
　　　　　　　　}
　　　　　　}
　　　　}
　　　　
　　　　// 如果有find中的字符在grid中不存在则返回0
　　　　for ( k=0; k< findStrLen; k++)
　　　　{
　　　　　　if ( vec[k].size() == 0 )
　　　　　　　　return 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;
　　　　　　}
　　　　}
　　　　
　　　　// 统计保存在最后位置向量中的点的count值
　　　　int count = 0;
　　　　for ( j=0; j < vec[findStrLen-1].size(); j++)
　　　　{
　　　　　　POS cur = vec[findStrLen-1][j];
　　　　　　count += cur.count;
　　　　　　if (count > 1000000000 )
　　　　　　　　return -1;
　　　　}
　　　　return count;
　　}
　　
　　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;
　　}
};　　　　三、小结

1、我的解题思路尤其是统计那一块多少参考了以前学过的运筹学中的动态规划的思路。

2、遍历grid中的每一个字符的算法若改动为如下的代码：for ( i = 0; i < gridSize; i ++)
{
　　for ( j= 0; j < grid[i].length(); j++)
　　{
　　 ....　　　　则即使grid中每个字符串的个数即使不同，如：“A”,
"CDEF",
"FDGGG",

也照样可以计算。