一道 Google 竞赛题的解法

核心提示： 二、我的解题步骤第一步.使用人脑按照题目要求，实际计算一遍，一道 Google 竞赛题的解法(2)，这里先用例1为例，在例1的find字符串的第一个字符是''A'',我们可以看到在相应的grid中，而数据个数又不确定(如例1中grid里A出现的位置有2处，而

二、我的解题步骤

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

这里先用例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重定义了这种保存位置的向量的数据类型：