bood:lz好像考虑的太复杂了
用动态规划，直接两个50*50矩阵从字符串末尾开始计算就可以了
(发表于2005-12-16 23:04:00)
txqc4:to bood 能否发段用动态规划解决的代码，让大家一起参考参考啊
(发表于2005-12-17 0:01:00)
bood:太长了，评论里发不上来。。。
我大致讲讲思路把，n个50*50矩阵m[n][50][50]（1..n，n为find长度），比如字符串ABCD
1. 对所有满足grid[x][y]=D的xy，m[n][x][y]=1
2. 对所有满足grid[x][y]=C的xy，m[n-1][x][y]=m[n]中x,y周围八个值得和
3. 对所有满足grid[x][y]=B的xy，m[n-2][x][y]=m[n-1]中x,y周围八个值得和
4. ...（如此类推即可）
由于每次只涉及两个矩阵的运算，可以只用两个矩阵
(发表于2005-12-17 9:50:00)
txqc4:谢谢您的思路，终于让我明白下面的代码
int countPaths(vector grid, string find)
{ const int MAXN = 1000000000;
const int dx[] = {0, 0,1,1, 1,-1,-1,-1};
const int dy[] = {1,-1,1,0,-1, 1, 0,-1};
int m = grid.size(), n = grid[0].size(), nn = find.size();
int i,j,k,s,t, a[2][52][52] = {0};
for (k=0; k<=m; i++)
for (j=1; j<=n; j++)
{
t=0;
if (grid[i-1][j-1] == find[k])
{ i
f (k==0) t=1;
else
for (s=0; s<8; s++)
{ t += a[ k%2 ][ i+dx[s] ][ j+dy[s] ];
if (t > MAXN) t = MAXN+1;
}
}
a[1-k%2][i][j] = t;
}
t=0;
for (i=1; i<=m; i++) for (j=1; j<=n; j++)
{ t += a[nn%2][i][j];
if (t > MAXN) return -1;
}
return t;
}
(发表于2005-12-17 11:01:00)
bbwolf:构建dfa，也能解决这个问题，我没学过运筹学，但原理应该是一样的。
(发表于2005-12-18 18:30:00)
txqc4:to bbwolf:能把您的思路再说详细些吗？让大家一起参考参考啊
(发表于2005-12-18 20:48:00)
bbwolf:个人觉得，这应该属于词法分析的问题，输入字符串后会进行状态的转换。
////////////////////
123
456
789
///////////////////
先构造一个状态转换表(DFA)，比如5在输入字符a后会转换到状态1，9。5在输入字符b后会转换到状态3,7，以此类推，对每个状态都用所有的输入字符去分析，最后形成一个状态转换表。
模拟dfa(状态转换表)，对每个输入的字符inputchar，会利用刚才的状态转换表进行状态转换，并记录状态集到状态集路径之间的数量，当输入字符完成时(inputchar == eof)，把路径数量相乘，得出的就应该是路径数。具体的可以参考编译原理相关的书籍。
这个问题我并没有仔细分析，只是一个思路。
让各位见笑了:)
(发表于2005-12-19 11:39:00)
txqc4:to bbwolf:思路挺新颖的，要是有代码就更好了
(发表于2005-12-19 19:55:00)
H2o:看不明白lz后面的路径数量统计,lz你把每个点到下一个点的路径可能(count),乘起来不就是总数了吗?干吗到最后一个字符的向量中去累加?后面的代码很莫名,请指教!
(发表于2005-12-20 17:58:00)
txqc4:To H2o: 举个例子说明吧，grid={"ABCD","EHHE","ZZZZ"} find="ZEA",Z到两个E的路径有4条，但最终只有左边那个E点最终能走到重点A。所以除了终点位置向量中的点外，其他位置向量中的统计(count)仅仅是可能，最纵能否通到最后一个点还不一定。
(发表于2005-12-20 19:58:00)
H2o:哦，原来是这个意思，thx。那倒过来搜索不是简单多了吗，得到的路径数就是真实的了，无用路径中途淘汰掉就可以了。
(发表于2005-12-21 10:54:00)
txqc4:To H2o: 正过来搜索和倒过来搜索原理是一样的，只是从起点数量少些的那一头开始可以少算些无用的路径
(发表于2005-12-21 19:37:00)
H2o:不好意思，这个我有点不明白了，题目要求的路径只是单向可达的，所以倒过来搜索，可以在每一轮立即排除无用的路径，这样就不用放到最后累加了是不是？（随便说说，没仔细想，也许程序实现并不简单）
(发表于2005-12-22 9:32:00)
H2o:sorry,楼主,因为随便说说,所以说错了,刚写完就觉得不对头,呵呵,没仔细看题目和你的代码,和数据结构,所以我把它当成有向图了,在题目的限定下你的方法是挺不错的.
(发表于2005-12-22 9:48:00)
txqc4:To H2o:谢谢鼓励。
(发表于2005-12-22 20:16:00)
kolvin:大家都好厉害啊！我是个初学的菜鸟，不过感谢楼主讲的这么详细，我大致能看懂！！！至于上面的第二段代码比较难懂啊！能否讲详细点啊？
(发表于2006-5-22 15:41:00)
txqc4:To kolvin,你说的第二段代码是指哪段代码啊？
(发表于2006-6-26 9:38:00)
xueylse:LZ猛呀，佩服。
(发表于2007-7-19 14:48:00)
兔狸熊://main.cpp
#include
#include "WordPath.h"
void main(void)
{
WordPath test;
string str("ABCDEFGHI");
vector vtest;
vtest.push_back("ABC");
vtest.push_back("FED");
vtest.push_back("GHI");
// string str("ABABABBA");
// vector vtest;
// vtest.push_back("ABABA");
// vtest.push_back("BABAB");
// vtest.push_back("ABABA");
// vtest.push_back("BABAB");
// vtest.push_back("ABABA");
// string str("AAAAAAAAAAA"); //only the test case take too much times,need update the code to fix the issue
// vector vtest;
// vtest.push_back("AAAAA");
// vtest.push_back("AAAAA");
// vtest.push_back("AAAAA");
// vtest.push_back("AAAAA");
// vtest.push_back("AAAAA");
int nFindTotalPaths = test.countPaths(vtest,str);
cout<<"findPaths:"< system("pause");
}
(发表于2007-10-22 12:45:00)
兔狸熊:#pragma once
#include
#include
using namespace std;
#define MAX_ELEMENT 50
enum PositionType
{
SIDE_LEFT = 0x0001,
SIDE_TOP = 0x0002,// SIDE need remember five sub element; X Self X
// X X X
SIDE_RIGHT = 0x0004,
SIDE_BOTTOM = 0x0008,
VERTEX_LEFT_TOP = SIDE_LEFT | SIDE_TOP,// this type need remember three sub element; self X
// X X
VERTEX_RIGHT_TOP = SIDE_RIGHT | SIDE_TOP,
VERTEX_LEFT_BOTTOM = SIDE_LEFT | SIDE_BOTTOM,
VERTEX_RIGHT_BOTTOM = SIDE_RIGHT | SIDE_BOTTOM,
CENTER = !( SIDE_LEFT | SIDE_TOP | SIDE_BOTTOM | SIDE_RIGHT),
// CENTER need remember eight sub element X X X
// X Self X
// X X X
};
typedef int Row;
typedef int Col;
typedef pair PairInt;
typedef vector FindVector;
(发表于2007-10-22 12:46:00)
兔狸熊:class CSubMap
{
public:
CSubMap(char * pWhole,int nRow,int nCol,PositionType nType);
~CSubMap();
FindVector FindChar(char chFind);
public:
char m_00,m_01,m_02;
char m_10,m_11,m_12;// m_11 is the find char self,so this position always is N/A
char m_20,m_21,m_22;
int m_nType;
int m_nRow;
int m_nCol;
};
class WordPath
{
public:
WordPath(void);
virtual ~WordPath(void);
public:
int countPaths(vector < string> grid, string find);
private:
void ClearWholeMap(void);
void BuildWholeMap(void);
void ClearSubMap(void);
void BuildSubMap(void);
PositionType GetPositionType(int nRow,int nCol);
int FindPaths(void);
int RecFindPaths(int nRow,int nCol,int nFindCharIndex);
private:
int m_nRow;
int m_nCol;
string m_strFind;
vector m_vSubMap;
vector m_vGrid;
char m_pWholeGrid[MAX_ELEMENT][MAX_ELEMENT];
};
(发表于2007-10-22 12:47:00)
兔狸熊:#include ".\wordpath.h"
CSubMap::CSubMap(char * pWhole,int nRow,int nCol,PositionType nType):
m_00(0),m_01(0),m_02(0),
m_10(0),m_11(0),m_12(0),
m_20(0),m_21(0),m_22(0)
{
if (pWhole)
{
char * pCurPosition = pWhole + nRow * MAX_ELEMENT + nCol;
m_nType = nType;
m_nRow = nRow;
m_nCol = nCol;
switch(nType)
{
case VERTEX_LEFT_TOP:
{
m_01 = *(pCurPosition + 1);
m_10 = *(pCurPosition + MAX_ELEMENT);
m_11 = *(pCurPosition + MAX_ELEMENT + 1);
}
break;
case VERTEX_RIGHT_TOP:
(发表于2007-10-22 12:47:00)
兔狸熊: case VERTEX_RIGHT_TOP:
{
m_01 = *(pCurPosition - 1);
m_11 = *(pCurPosition + MAX_ELEMENT - 1);
m_12 = *(pCurPosition + MAX_ELEMENT);
}
break;
case VERTEX_LEFT_BOTTOM:
{
m_10 = *(pCurPosition - MAX_ELEMENT );
m_11 = *(pCurPosition - MAX_ELEMENT + 1);
m_21 = *(pCurPosition + 1);
}
break;
case VERTEX_RIGHT_BOTTOM:
{
m_11 = *(pCurPosition - MAX_ELEMENT - 1);
m_12 = *(pCurPosition - MAX_ELEMENT);
m_21 = *(pCurPosition - 1);
}break;
case SIDE_LEFT:
{
m_00 = *(pCurPosition - MAX_ELEMENT);
m_01 = *(pCurPosition - MAX_ELEMENT + 1);
m_11 = *(pCurPosition + 1);
m_20 = *(pCurPosition + MAX_ELEMENT );
m_21 = *(pCurPosition + MAX_ELEMENT + 1);
}break;
(发表于2007-10-22 12:48:00)
兔狸熊: case SIDE_TOP:
{
m_00 = *(pCurPosition - 1);
m_02 = *(pCurPosition + 1);
m_10 = *(pCurPosition + MAX_ELEMENT - 1);
m_11 = *(pCurPosition + MAX_ELEMENT);
m_12 = *(pCurPosition + MAX_ELEMENT + 1);
}break;
case SIDE_RIGHT:
{
m_01 = *(pCurPosition - MAX_ELEMENT - 1);
m_02 = *(pCurPosition - MAX_ELEMENT);
m_11 = *(pCurPosition - 1);
m_21 = *(pCurPosition + MAX_ELEMENT - 1);
m_22 = *(pCurPosition + MAX_ELEMENT);
}break;
(发表于2007-10-22 12:49:00)
兔狸熊: case SIDE_BOTTOM:
{
m_10 = *(pCurPosition - MAX_ELEMENT - 1);
m_11 = *(pCurPosition - MAX_ELEMENT);
m_12 = *(pCurPosition - MAX_ELEMENT + 1);
m_20 = *(pCurPosition - 1);
m_22 = *(pCurPosition + 1);
}break;
case CENTER:
{
m_00 = *(pCurPosition - MAX_ELEMENT - 1);
m_01 = *(pCurPosition - MAX_ELEMENT);
m_02 = *(pCurPosition - MAX_ELEMENT + 1);
m_10 = *(pCurPosition - 1);
m_12 = *(pCurPosition + 1);
m_20 = *(pCurPosition + MAX_ELEMENT - 1);
m_21 = *(pCurPosition + MAX_ELEMENT);
m_22 = *(pCurPosition + MAX_ELEMENT + 1);
}break;
}
}
}
(发表于2007-10-22 12:49:00)
兔狸熊:FindVector CSubMap::FindChar(char chFind)
{
FindVector vFind;
switch(m_nType)
{
case VERTEX_LEFT_TOP:
{
if (chFind == m_01)
vFind.push_back(make_pair(m_nRow,m_nCol + 1));
if (chFind == m_10)
vFind.push_back(make_pair(m_nRow + 1,m_nCol));
if (chFind == m_11)
vFind.push_back(make_pair(m_nRow + 1,m_nCol + 1));
}
break;
case VERTEX_RIGHT_TOP:
{
if (chFind == m_01)
vFind.push_back(make_pair(m_nRow ,m_nCol - 1));
if (chFind == m_11)
vFind.push_back(make_pair(m_nRow + 1,m_nCol - 1));
if (chFind == m_12)
vFind.push_back(make_pair(m_nRow + 1,m_nCol));
}
break;
(发表于2007-10-22 12:49:00)
兔狸熊:case VERTEX_LEFT_BOTTOM:
{
if (chFind == m_10)
vFind.push_back(make_pair(m_nRow - 1,m_nCol));
if (chFind == m_11)
vFind.push_back(make_pair(m_nRow - 1,m_nCol + 1));
if (chFind == m_21)
vFind.push_back(make_pair(m_nRow , m_nCol + 1));
}
break;
case VERTEX_RIGHT_BOTTOM:
{
if (chFind == m_11)
vFind.push_back(make_pair(m_nRow - 1, m_nCol - 1));
if (chFind == m_12)
vFind.push_back(make_pair(m_nRow - 1,m_nCol));
if (chFind == m_21)
vFind.push_back(make_pair(m_nRow,m_nCol - 1));
}break;
case SIDE_LEFT:
{
if (chFind == m_00)
vFind.push_back(make_pair(m_nRow - 1, m_nCol));
if (chFind == m_01)
vFind.push_back(make_pair(m_nRow - 1, m_nCol + 1));
if (chFind == m_11)
vFind.push_back(make_pair(m_nRow,m_nCol + 1));
if (chFind == m_20)
vFind.push_back(make_pair(m_nRow + 1,m_nCol));
if (chFind == m_21)
vFind.push_back(make_pair(m_nRow + 1,m_nCol + 1));
}break;
(发表于2007-10-22 12:49:00)
兔狸熊: case SIDE_TOP:
{
if (chFind == m_00)
vFind.push_back(make_pair(m_nRow, m_nCol - 1));
if (chFind == m_02)
vFind.push_back(make_pair(m_nRow, m_nCol + 1));
if (chFind == m_10)
vFind.push_back(make_pair(m_nRow + 1 , m_nCol - 1));
if (chFind == m_11)
vFind.push_back(make_pair(m_nRow + 1 , m_nCol ));
if (chFind == m_12)
vFind.push_back(make_pair(m_nRow + 1, m_nCol + 1));
}break;
case SIDE_RIGHT:
{
if (chFind == m_01)
vFind.push_back(make_pair(m_nRow - 1 , m_nCol - 1));
if (chFind == m_02)
vFind.push_back(make_pair(m_nRow - 1 , m_nCol));
if (chFind == m_11)
vFind.push_back(make_pair(m_nRow , m_nCol - 1));
if (chFind == m_21)
vFind.push_back(make_pair(m_nRow + 1 , m_nCol - 1));
if (chFind == m_22)
vFind.push_back(make_pair(m_nRow + 1 , m_nCol));
}break;
(发表于2007-10-22 12:50:00)
兔狸熊:case SIDE_BOTTOM:
{
if (chFind == m_10)
vFind.push_back(make_pair(m_nRow - 1 , m_nCol - 1));
if (chFind == m_11)
vFind.push_back(make_pair(m_nRow - 1 , m_nCol ));
if (chFind == m_12)
vFind.push_back(make_pair(m_nRow - 1 , m_nCol + 1));
if (chFind == m_20)
vFind.push_back(make_pair(m_nRow , m_nCol - 1));
if (chFind == m_22)
vFind.push_back(make_pair(m_nRow , m_nCol + 1));
}break;
(发表于2007-10-22 12:51:00)
兔狸熊:case CENTER:
{
if (chFind == m_00)
vFind.push_back(make_pair(m_nRow - 1 ,m_nCol - 1));
if (chFind == m_01)
vFind.push_back(make_pair(m_nRow - 1 , m_nCol));
if (chFind == m_02)
vFind.push_back(make_pair(m_nRow - 1 , m_nCol + 1));
if (chFind == m_10)
vFind.push_back(make_pair(m_nRow , m_nCol - 1));
if (chFind == m_12)
vFind.push_back(make_pair(m_nRow, m_nCol + 1));
if (chFind == m_20)
vFind.push_back(make_pair(m_nRow + 1 , m_nCol - 1));
if (chFind == m_21)
vFind.push_back(make_pair(m_nRow + 1 , m_nCol));
if (chFind == m_22)
vFind.push_back(make_pair(m_nRow + 1 , m_nCol + 1));
}break;
}
return vFind;
}
(发表于2007-10-22 12:52:00)
兔狸熊:CSubMap::~CSubMap()
{
}
WordPath::WordPath(void)
{
}
WordPath::~WordPath(void)
{
ClearWholeMap();
ClearSubMap();
}
(发表于2007-10-22 12:52:00)
兔狸熊:PositionType WordPath::GetPositionType(int nRow,int nCol)
{
if (nRow > 0 && nRow < m_nRow && nCol > 0 && nCol < m_nCol)
return CENTER;
int nRetType = 0;
if (nRow == 0)
{
nRetType |= SIDE_TOP;
}
else if (nRow == m_nRow - 1)
{
nRetType |= SIDE_BOTTOM;
}
if (nCol == 0)
{
nRetType |= SIDE_LEFT;
}
else if (nCol == m_nCol - 1)
{
nRetType |= SIDE_RIGHT;
}
return (PositionType)nRetType;
}
void WordPath::ClearWholeMap()
{
memset(m_pWholeGrid,0,MAX_ELEMENT*MAX_ELEMENT);
}
void WordPath::BuildWholeMap()
{
ClearWholeMap();
for (int i = 0; i < m_nRow; i++)
{
memcpy(m_pWholeGrid[i],m_vGrid[i].c_str(),m_vGrid[i].size());
}
}
(发表于2007-10-22 12:52:00)
兔狸熊:void WordPath::ClearSubMap()
{
vector::iterator iter = m_vSubMap.begin();
for (; iter != m_vSubMap.end() ; iter++)
{
delete (*iter);
}
m_vSubMap.clear();
}
void WordPath::BuildSubMap(void)
{
ClearSubMap();
for (int nRow = 0; nRow < m_nRow ; nRow ++)
{
for (int nCol = 0 ; nCol < m_nCol ; nCol ++)
{
m_vSubMap.push_back(new CSubMap((char*)m_pWholeGrid,nRow,nCol,GetPositionType(nRow,nCol)));
}
}
}
(发表于2007-10-22 12:52:00)
兔狸熊:int WordPath::RecFindPaths(int nRow,int nCol,int nFindCharIndex)
{
if (nFindCharIndex >= m_strFind.size() -1 )
return 1;
FindVector vFind;
nFindCharIndex++;
int nTotalNum = 0;
vFind = m_vSubMap[nRow * m_nRow + nCol]->FindChar(m_strFind[nFindCharIndex]);
FindVector ::iterator iter = vFind.begin();
for (; iter != vFind.end() ; iter++)
{
nTotalNum += RecFindPaths((*iter).first,(*iter).second,nFindCharIndex);
if (nTotalNum > 1000000000)
return -1;
}
return nTotalNum;
}
int WordPath::FindPaths()
{
int nTotolCount = 0;
for (int nRow = 0; nRow < m_nRow ; nRow++)
{
for (int nCol = 0; nCol < m_nCol ; nCol++)
{
if (m_pWholeGrid[nRow][nCol] == m_strFind[0])
{
if (nTotolCount > 1000000000)
return -1;
nTotolCount += RecFindPaths(nRow,nCol,0);
}
}
}
if (nTotolCount > 1000000000)
return -1;
return nTotolCount;
}
(发表于2007-10-22 12:53:00)
兔狸熊:int WordPath::countPaths(vector < string> grid, string find)
{
m_strFind = find;
m_nRow = grid.size();
m_vGrid = grid;
m_nCol = m_nRow;
BuildWholeMap();
BuildSubMap();
return FindPaths();
}
(发表于2007-10-22 12:53:00)
兔狸熊:把上面的代码了，再帖一次，对于Test case 5的速度提高了一些了。
(发表于2007-10-22 22:05:00)
兔狸熊:#pragma once
#include
#include
using namespace std;
#define MAX_ELEMENT 50
enum PositionType
{
SIDE_LEFT = 0x0001,
SIDE_TOP = 0x0002,
SIDE_RIGHT = 0x0004,
SIDE_BOTTOM = 0x0008,
VERTEX_LEFT_TOP = SIDE_LEFT | SIDE_TOP,
VERTEX_RIGHT_TOP = SIDE_RIGHT | SIDE_TOP,
VERTEX_LEFT_BOTTOM = SIDE_LEFT | SIDE_BOTTOM,
VERTEX_RIGHT_BOTTOM = SIDE_RIGHT | SIDE_BOTTOM,
CENTER = !( SIDE_LEFT | SIDE_TOP | SIDE_BOTTOM | SIDE_RIGHT),
};
(发表于2007-10-22 22:06:00)
兔狸熊:class WordPath
{
public:
WordPath(void);
virtual ~WordPath(void);
public:
int countPaths(vector < string> grid, string find);
private:
void ClearWholeMap(void);
void BuildWholeMap(void);
int GetPositionType(int nRow,int nCol);
int FindPaths(void);
int RecFindPaths(int nRow,int nCol,int nFindCharIndex);
void RecFindPaths(int nRow,int nCol,int nFindCharIndex,int &nSum);
private:
int m_nRow;
int m_nCol;
string m_strFind;
int m_nStrLen;
vector m_vGrid;
char m_pWholeGrid[MAX_ELEMENT][MAX_ELEMENT];
};
(发表于2007-10-22 22:06:00)
兔狸熊:#include ".\wordpath.h"
WordPath::WordPath(void){}
WordPath::~WordPath(void){ClearWholeMap();}
int WordPath::GetPositionType(int nRow,int nCol)
{
if (nRow > 0 && nRow < m_nRow - 1 && nCol > 0 && nCol < m_nCol - 1)
return CENTER;
int nRetType = 0;
if (nRow == 0)
{
nRetType |= SIDE_TOP;
}
else if (nRow == m_nRow - 1)
{
nRetType |= SIDE_BOTTOM;
}
if (nCol == 0)
{
nRetType |= SIDE_LEFT;
}
else if (nCol == m_nCol - 1)
{
nRetType |= SIDE_RIGHT;
}
return (PositionType)nRetType;
}
(发表于2007-10-22 22:07:00)
兔狸熊:
void WordPath::ClearWholeMap()
{
memset(m_pWholeGrid,0,MAX_ELEMENT*MAX_ELEMENT);
}
void WordPath::BuildWholeMap()
{
ClearWholeMap();
for (int i = 0; i < m_nRow; i++)
memcpy(m_pWholeGrid[i],m_vGrid[i].c_str(),m_vGrid[i].size());
}
void WordPath::RecFindPaths(int nRow,int nCol,int nFindCharIndex,int &nSum)
{
if (nSum > 1000000000 || nSum < 0)
{
nSum = -1;
return ;
}
bool bShouldEnd = (nFindCharIndex == m_nStrLen - 1);
char * pCurPosition =&m_pWholeGrid[nRow][nCol];
char chFind = m_strFind[nFindCharIndex];
int nType = GetPositionType(nRow,nCol);
(发表于2007-10-22 22:07:00)
兔狸熊: switch(nType)
{
case VERTEX_LEFT_TOP:
{
if (chFind == *(pCurPosition + 1) )
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow,nCol + 1,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + MAX_ELEMENT))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow + 1,nCol,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + MAX_ELEMENT + 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow + 1, nCol + 1,nFindCharIndex + 1,nSum);
}
}
break;
(发表于2007-10-22 22:08:00)
兔狸熊: case VERTEX_RIGHT_TOP:
{
if (chFind == *(pCurPosition - 1) )
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow,nCol - 1,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + MAX_ELEMENT - 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow + 1,nCol - 1 , nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + MAX_ELEMENT ))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow + 1, nCol ,nFindCharIndex + 1,nSum);
}
}
break;
(发表于2007-10-22 22:08:00)
兔狸熊: case VERTEX_LEFT_BOTTOM:
{
if (chFind == *(pCurPosition - MAX_ELEMENT ) )
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow - 1,nCol,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition - MAX_ELEMENT + 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow - 1,nCol + 1 ,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow , nCol + 1,nFindCharIndex + 1,nSum);
}
}
break;
(发表于2007-10-22 22:08:00)
兔狸熊:case VERTEX_RIGHT_BOTTOM:
{
if (chFind == *(pCurPosition - MAX_ELEMENT - 1 ) )
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow - 1,nCol - 1,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition - MAX_ELEMENT ))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow - 1,nCol ,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition - 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow , nCol - 1,nFindCharIndex + 1,nSum);
}
}break;
(发表于2007-10-22 22:08:00)
兔狸熊: case SIDE_LEFT:
{
if (chFind == *(pCurPosition - MAX_ELEMENT ) )
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow - 1,nCol , nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition - MAX_ELEMENT + 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow - 1,nCol + 1 ,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + 1))
{ if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow , nCol + 1,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + MAX_ELEMENT))
{ if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow + 1,nCol,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + MAX_ELEMENT + 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow + 1 , nCol + 1, nFindCharIndex + 1,nSum);
}
}break;
(发表于2007-10-22 22:09:00)
兔狸熊: case SIDE_TOP:
{
if (chFind == *(pCurPosition - 1 ) )
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow ,nCol - 1 , nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow ,nCol + 1 ,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + MAX_ELEMENT - 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow + 1 , nCol - 1,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + MAX_ELEMENT))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow + 1,nCol,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + MAX_ELEMENT + 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow + 1 , nCol + 1, nFindCharIndex + 1,nSum);
}
}break;
(发表于2007-10-22 22:09:00)
兔狸熊:case SIDE_RIGHT:
{
if (chFind == *(pCurPosition - MAX_ELEMENT - 1 ) )
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow - 1 ,nCol - 1 , nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition - MAX_ELEMENT ))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow - 1 ,nCol ,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition - 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow , nCol - 1,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + MAX_ELEMENT - 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow + 1,nCol - 1,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + MAX_ELEMENT ))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow + 1 , nCol, nFindCharIndex + 1,nSum);
}
}break;
(发表于2007-10-22 22:09:00)
兔狸熊: case SIDE_BOTTOM:
{
if (chFind == *(pCurPosition - MAX_ELEMENT - 1 ) )
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow - 1 ,nCol - 1 , nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition - MAX_ELEMENT ))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow - 1 ,nCol ,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition - MAX_ELEMENT + 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow - 1 , nCol + 1,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition - 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow ,nCol - 1,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow , nCol + 1, nFindCharIndex + 1,nSum);
}
}break;
(发表于2007-10-22 22:09:00)
兔狸熊: case CENTER:
{
if (chFind == *(pCurPosition - MAX_ELEMENT - 1 ) )
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow - 1 ,nCol - 1 , nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition - MAX_ELEMENT ))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow - 1,nCol ,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition - MAX_ELEMENT + 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow - 1 , nCol + 1,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition - 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow ,nCol - 1,nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow , nCol + 1, nFindCharIndex + 1,nSum);
}
(发表于2007-10-22 22:10:00)
兔狸熊: if (chFind == *(pCurPosition + MAX_ELEMENT - 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow + 1 , nCol + 1 ,nFindCharIndex + 1 ,nSum);
}
if (chFind == *(pCurPosition + MAX_ELEMENT))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow + 1 ,nCol , nFindCharIndex + 1,nSum);
}
if (chFind == *(pCurPosition + MAX_ELEMENT + 1))
{
if (bShouldEnd)
nSum++;
else
RecFindPaths(nRow + 1 , nCol + 1 , nFindCharIndex + 1,nSum);
}
}break;
}
}
(发表于2007-10-22 22:10:00)
兔狸熊:int WordPath::FindPaths()
{
int nTotalCount = 0;
for (int nRow = 0; nRow < m_nRow ; nRow++)
{
for (int nCol = 0; nCol < m_nCol ; nCol++)
{
if (m_pWholeGrid[nRow][nCol] == m_strFind[0])
{
if (nTotalCount > 1000000000 || nTotalCount == -1)
return -1;
RecFindPaths(nRow,nCol,1,nTotalCount);
}
}
}
return nTotalCount;
}
int WordPath::countPaths(vector < string> grid, string find)
{
m_strFind = find;
m_nRow = grid.size();
m_vGrid = grid;
m_nCol = m_nRow;
m_nStrLen = m_strFind.size();
BuildWholeMap();
return FindPaths();
}
(发表于2007-10-22 22:11:00)
..........................................................................
--------------------next---------------------
