一道 Google 竞赛题的解法

核心提示：本文示例源代码或素材下载 本人于2005年12月13日凌晨参加了google中国编程挑战赛的入围阶段的赛事，虽然最终我感觉自己做出了这道级别为high到mid间的赛题，一道 Google 竞赛题的解法，但是却发现那时入围赛事早已经结束了......相信 vckbase 中的不少朋友肯定也参加了那场入围赛，所以我

本文示例源代码或素材下载

本人于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。