h***r
发帖数: 22 | 1 在一个n*n的字符矩阵上,问有多少个有效的字符串.一个有效的字符串可以从矩阵中任
何一个字符开始,到任何一个字符结束.下一个字符是上一个字符8个相邻字符中的一个.
而且字符不能重复使用.
说明一下，不是问编程，而是要求字符串数对于n的表达式。如果没有确切解，可以近
似用O(n...)表达 | b*****u
发帖数: 648 | 2 int ValidWords ( char[][]matrix, int n, map dictionary)
{
int result = 0;
//every element as starting point
for(int i = 0; i< n; i++)
{
for (int j = 0; j
{
map usage;
string testWord;
testWord += matrix[i][j];
usage[i*n+j]=1;
moveNext (testWord; i, j, dictionary,usage,result);
}
}
return result;
}
// move to next step
void moveNext (string testWord, int i, int j, map & usage map<
string,int>&dictionary,
int& result)
{
// look up
if (dictionary.find(testWord) != dictionary.end())
{ result++; }
int len = testWord.length();
// the direction is valid and not duplicate
if (i-1 < n && (usage.find((i-1)*n+j))==usage.end())
{
testWord += matrix[i-1][j];
moveNext (testWord, i-1, j, dictionary,usage result);
testWord.erase(len-1);
}
if (i+1
{
testWord += matrix[i+1][j];
moveNext (testWord, i+1, j, dictionary,usage result);
testWord.erase(len-1);
}
if (j-1
{
testWord += matrix[i][j-1];
moveNext (testWord, i, j-1, dictionary,usage ,result);
testWord.erase(len-1);
}
... ... | h***r
发帖数: 22 | 3 说明一下，不是问编程，而是要求字符串数对于n的表达式。如果没有确切解，可以近
似用O(n...)表达 | s***u
发帖数: 101 | 4 可以将这个矩阵转换成一个图， 任何相邻的两个字符，如果在8个字符区域内，则有一
条边。
假设这个图有m个联通区域，每个联通区域内有ki 个字符，那一共有
k1*k1 + k2* k2 + ... + km*km 个有效字符。
不知道这样对不对
个.
【在 h***r 的大作中提到】
: 在一个n*n的字符矩阵上,问有多少个有效的字符串.一个有效的字符串可以从矩阵中任
: 何一个字符开始,到任何一个字符结束.下一个字符是上一个字符8个相邻字符中的一个.
: 而且字符不能重复使用.
: 说明一下，不是问编程，而是要求字符串数对于n的表达式。如果没有确切解，可以近
: 似用O(n...)表达
| h***r
发帖数: 22 | 5 换句话说，也就是问譬如二楼这样一个算法的算法复杂性。 | b*****u
发帖数: 648 | | r****c
发帖数: 2585 | 7 why < 4^n
I think it is something like o(n^n)
【在 b*****u 的大作中提到】
: 大于 n^2 小于 4^n ?
| h***r
发帖数: 22 | | s*********6
发帖数: 261 | | H****s
发帖数: 247 | |
|
