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 | |||||||||||||
| |||||||||||||
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) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||
| 4) | |||||||||||||
| |||||||||||||
| 5) | |||||||||||||
| |||||||||||||
| 6) | |||||||||||||
| |||||||||||||
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代码
#include <vector>
#include <string>
using namespace std;
class WordPath{
private:
long inva; //标志，如果超过1000000000则设置其标志位直接退出循环
char mm[50][50]; //地图用的二维数组，不用向量和string是因为这样比较快
long emap[50][50][50]; //剪枝用的三维数组
char findstr[51]; //路径
long strsize;
long r;
long findit(int i,int j,int index)
{
long w=0;
if(inva)
return 0;
if(i<0 || j<0 || i>r || j>r) //数组的边缘检测
return 0;
if(emap[i][j][index]!=-1)
return emap[i][j][index];
if(mm[i][j]==findstr[index])
{
if(index+1==strsize)
return 1;
w =findit(i-1,j-1,index+1); //遍历边缘的八个单元
w+=findit(i ,j-1,index+1);
w+=findit(i+1,j-1,index+1);
w+=findit(i-1,j ,index+1);
w+=findit(i+1,j ,index+1);
w+=findit(i-1,j+1,index+1);
w+=findit(i ,j+1,index+1);
w+=findit(i+1,j+1,index+1);
if(w>1000000000)
return inva=1;
emap[i][j][index]=w; //保存此处在查找第n个元素时路径的个数
return w;
}
else
return 0;
};
public:
int countPaths(vector <string> grid, string find)
{
long i=0,j=0,k;
long w=0;
inva=0;
//初始化变量
r=grid.size()-1;
strcpy (findstr,find.c_str());
strsize=find.size();
for(i=0;i<=r;i++)
for(j=0;j<grid[0].size();j++)
{
mm[i][j]=grid[i][j];
for(k=0;k<strsize;k++)
emap[i][j][k]=-1;
}
//在各个位置进行递归运算
for(i=0;i<=r;i++)
for(j=0;j<grid[0].size();j++)
{
w+=findit(i,j,0);
if(inva || w>1000000000)
return -1;
}
return w;
};
};
评论