Google 竞赛题WordPath的解法

本人于2005年12月13日凌晨参加了google中国编程挑战赛的入围阶段的赛事。虽然最终我感觉自己做出了这道级别为high到mid间的赛题，但是却发现那时入围赛事早已经结束了......
　　相信 vckbase 中的不少朋友肯定也参加了那场入围赛，所以我打算把自己的解法写出来，一则虽然题目中的测试用例是全部通过了，但这并不能保证我的解法是正确的，希望大家批评指教；二则相信其他朋友也一定有更好的解法大家一起讨论讨论。希望，这篇文章能起到抛砖引玉的效果。

一、竞赛题目

Problem Statement
You are given a String[] grid representing a rectangular grid of letters. You are also given a String find,
a word you are to find within the grid. The starting point may be anywhere in the grid. The path may move
up, down, left, right, or diagonally from one letter to the next, and may use letters in the grid more than
once, but you may not stay on the same cell twice in a row (see example 6 for clarification).
You are to return an int indicating the number of ways find can be found within the grid. If the result is
more than 1,000,000,000, return -1.

Definition
Class:
WordPath
Method:
countPaths
Parameters:
vector < string >, string
Returns:
int
Method signature:
int countPaths(vector < string> grid, string find)
(be sure your method is public)

Constraints
-
grid will contain between 1 and 50 elements, inclusive.
-
Each element of grid will contain between 1 and 50 uppercase (''A''-''Z'') letters, inclusive.
-
Each element of grid will contain the same number of characters.
-
find will contain between 1 and 50 uppercase (''A''-''Z'') letters, inclusive.

Examples
0)
{"ABC",
"FED",
"GHI"}
"ABCDEFGHI"
Returns: 1
There is only one way to trace this path. Each letter is used exactly once.

1)
{"ABC",
"FED",
"GAI"}
"ABCDEA"
Returns: 2
Once we get to the ''E'', we can choose one of two directions for the final ''A''.

2)
{"ABC",
"DEF",
"GHI"}
"ABCD"
Returns: 0
We can trace a path for "ABC", but there''s no way to complete a path to the letter ''D''.

3)
{"AA",
"AA"}
"AAAA"
Returns: 108
We can start from any of the four locations. From each location, we can then move in any of the three
possible directions for our second letter, and again for the third and fourth letter. 4 * 3 * 3 * 3 = 108.

4)
{"ABABA",
"BABAB",
"ABABA",
"BABAB",
"ABABA"}
"ABABABBA"
Returns: 56448
There are a lot of ways to trace this path.

5)
{"AAAAA",
"AAAAA",
"AAAAA",
"AAAAA",
"AAAAA"}
"AAAAAAAAAAA"
Returns: -1
There are well over 1,000,000,000 paths that can be traced.

6)
{"AB",
"CD"}
"AA"
Returns: 0
Since we can''t stay on the same cell, we can''t trace the path at all.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or
reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited.
(c)2003, TopCoder, Inc. All rights reserved.

题目的意思大致是这样的：在类 WordPath 中编写一个原型为：

int countPaths(vector < string> grid, string find);

的函数，grid相当于一个字母矩阵，grid中的每个字符串含有相同个数的字母，这些字母都是大写的字母,从''A''到''Z''，grid中字母个数的范围是1-50。参数find是要求你在grid中搜索路径的字符串，其同样只含有''A''到''Z''的字符，其个数范围同样是1-50。搜索起点可以从grid中的任何一点开始，然后可以向上，向下，向左，向右，以及对角线移动一格。grid中的每个位置的字母可以多次使用。但路径不能在相同位置停留两次(见用例6)。返回值是个整型数据，表示搜索到的路径总数数。如果这个数值大于1,000,000,000, 则返回-1。

二、我的解题步骤

第一步.使用人脑按照题目要求，实际计算一遍。

　　这里先用例1为例。在例1的find字符串的第一个字符是''A'',我们可以看到在相应的grid中，''A''在两个位置上出现，由于起点不限，所以我们搜索到的起点有2个；find的第2个字符是B，我们可以看到grid中只出现了1个B,而按照题目要求移动的话，显然只有左上角的那个A可以移动到这个B的位置。我们以次类推一值移动到E,都是唯一一条路经，但最后一个字符还是A,这时按照题目要求，2个A都可以从E移动到达，并且题目也说明每个位置可以多次移动停留，所以这时2个A都符合条件。这样find在grid中的移动路径共有2条，即返回值为2。

第二步，把上述思维过程，转化为计算机模型。

1、处理find中每个字符在grid中出现的位置

1.1 数据结构

1.1.1
　　我们可以看到find中的每个位置的字母可以在grid中多次出现，所以我们有必要把这些位置都纪录下来以便下一步的判断。grid中的每个字母可以这样标记其位置：以字符串序列为纵坐标(0开始)，以字母在字符串中的位置为横坐标(0开始)。如用例1中的2个A的位置可以用(0,1)和(1,2)标记。我定义一个结构纪录在grid中的位置：

typedef struct POINTtag{
    int x;
    int y;
    int count;
}POS;

y表示在grid中的第几个字符串，x表示在字符串中的第几个字符。字段count在下文中再说明。

1.1.2
　　要保存多个位置数据，而数据个数又不确定(如例1中grid里A出现的位置有2处，而在例4中grid里A出现的位置有13处)，显然使用向量(vector)保存这些位置较为合适。我用typedef重定义了这种保存位置的向量的数据类型：

typedef vector< POS > VETPOS; 

find 中的每一个字符都有必要使用一个VETPOS类型的变量保存其在相应grid中出现的位置，这些变量的个数显然应该和find字符串的长度相等。假设 find的长度用变量int findStrLen表示，则findStrLen = find.length()。这些VETPOS类型的变量的处理和计算的过程大多相同，显然可以使用数组来集中处理。但由于每次调用的find字符串的长度未必都相等，所以这些VETPOS类型的变量同样保存到向量(vector)中更合适。代码中我是这样定义的：

int findStrLen = find.length();
vector < VETPOS > vec(findStrLen);

这样保存find第k个字符在grid中出现位置的向量可以用vec[k]表示了。

1.2　算法

　　数据结构至此定义的差不多了，接着就该考虑如何遍历grid的每一个字母，并将在find中出现的字符的位置保存到相应的位置向量中去。

1.2.1
　　在grid中其第i个字符串可以用grid[i]表示；而在string中其第几个字符可以用成员函数at(),或者重载运算符[]取得，如find 的第i个字符可以用find.at(i)或者find[i]来获得。所以在grid中取得位置为(0,1)的字符可以用表达式grid[1][0]或者 grid[1].at(0)取得。要遍历grid的每一个字母，首先要知道grid中字符串的个数，这可以调用vector的size成员函数取得，假设 grid中的字符串个数为int gridSize,则gridSize=grid.size()；而字符串的长度可以用string的成员函数length()取得，由于题中明确告诉我们，grid中的每个字符长度相等，所以我们只要计算其中任意一个字符串长度即可。假设grid中的每个字符长度为int gridStrLen，则gridStrLen = grid[0].length()。知道了grid中每个字符串的字符个数和总的字符串个数，我们就可以用2个嵌套的for循环遍历其中的每一个字符,代码如下：

for ( int i = 0; i < gridSize; i ++)
{
    for ( int j= 0; j < gridStrLen; j++)
    {
       char ch = grid[i].at(j);
       ........
    }
}	

1.2.2
　　在遍历的过程中将grid的每个位置的字符，和find中的每一个字符比较，如果相等则把该字符的位置保存到find相应位置的向量中去。假设find中的第k个字符，与grid中(j,i)处的字符相等，即if ( find[k] == grid[i].at(j) ),则把当前的位置即(j,i)保存到vec[k]中去。结合遍历grid的代码，取得find中每个字符在grid中的位置的代码如下：

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);
            }
        }
    }
}		

2、寻找满足find字符串的路径

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的实现将在下文描述。

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、统计所有符合条件的路径总数

　　经过上述代码的运算，保存在最后的位置向量中的每一个点的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（[e-mail]）
//日期：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",

也照样可以计算。