一道Google競賽題的解法

本人於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（[email protected]）
//日期：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",

也照樣可以計算。

本文配套源碼