考虑以下内容:
这里的
任务是在方格图中查找给定字符串。条件是给定字符串中的所有字符应该是相邻的,并且方格图中的任何一个字符都不能重复使用以构建给定字符串。
我提出了一个简单的回溯解决方案,解决方案非常快,但最坏情况时间确实很糟糕。
例如:假设方格图是4x4,填满了所有的a,因此有16个a,要查找的字符串是aaaaaaaaaaaaaaab,即15个a和一个b。其中一种方法是消除不在方格图中出现的字符的字符串。但是最坏情况仍然可能出现,例如方格图是abababababababab,要查找的字符串是abababababababbb。
我的尝试如下: https://ideone.com/alUPf:
a c p r c
x s o p c
v o v n i
w g f m n
q a t i t
如果在方块中,一个字母 i_index
在任意一个以下位置与另一个字母 j_index
相邻,即 i_index
与 j_index
在下列位置相邻:
* * *
* x *
* * *
这里的
*
表示与x
相邻的位置。任务是在方格图中查找给定字符串。条件是给定字符串中的所有字符应该是相邻的,并且方格图中的任何一个字符都不能重复使用以构建给定字符串。
我提出了一个简单的回溯解决方案,解决方案非常快,但最坏情况时间确实很糟糕。
例如:假设方格图是4x4,填满了所有的a,因此有16个a,要查找的字符串是aaaaaaaaaaaaaaab,即15个a和一个b。其中一种方法是消除不在方格图中出现的字符的字符串。但是最坏情况仍然可能出现,例如方格图是abababababababab,要查找的字符串是abababababababbb。
我的尝试如下: https://ideone.com/alUPf:
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 5
int sp (char mat[MAX][MAX], char *pat, int c, int i, int j)
{
int r = 0;
char temp;
if (c == strlen (pat))
return 1;
if (((i<0) || (j<0)) || (i>=MAX) || (j>=MAX))
return 0;
if (mat[i][j] != pat[c])
return 0;
if (isupper (mat[i][j]))
return 0;
/* Save character and mark location to indicate
* DFS has visited this node, to stop other branches
* to enter here and cross over path
*/
temp = mat[i][j];
mat[i][j] = 0;
r |= sp (mat, pat, c+1, i-1, j-1);
r |= sp (mat, pat, c+1, i-1, j);
r |= sp (mat, pat, c+1, i-1, j+1);
r |= sp (mat, pat, c+1, i, j+1);
r |= sp (mat, pat, c+1, i+1, j+1);
r |= sp (mat, pat, c+1, i+1, j);
r |= sp (mat, pat, c+1, i+1, j-1);
r |= sp (mat, pat, c+1, i, j-1);
/* restore value */
mat[i][j] = temp;
/* mark if success */
if ((mat[i][j] == pat[c]) && (r == 1))
mat[i][j] = toupper (mat[i][j]);
return r;
}
/* Testing the `sp` module */
int main (void)
{
char mat[MAX][MAX] = {
{'a', 'c', 'p', 'r', 'c'},
{'x', 's', 'o', 'p', 'c'},
{'v', 'o', 'v', 'n', 'i'},
{'w', 'g', 'f', 'm', 'n'},
{'q', 'a', 't', 'i', 't'}
};
char pat[] = "microsoft";
int i, j;
for (i=0; i<5; i++)
{
for (j=0; j<5; j++)
printf ("%c ", mat[i][j]);
printf ("\n");
}
for (i=0; i<5; i++)
for (j=0; j<5; j++)
sp (mat, pat, 0, i, j);
printf ("\n\n\n");
for (i=0; i<5; i++)
{
for (j=0; j<5; j++)
{
if (isupper (mat[i][j]))
printf ("%c ", mat[i][j]);
else
printf (". ");
}
printf ("\n");
}
printf ("\n");
return 0;
}
这将输出:
a c p r c
x s o p c
v o v n i
w g f m n
q a t i t
. . . R .
. S O . C
. O . . I
. . F M .
. . T . .
函数sp
执行工作,执行回溯。
是否有更好的方法?或者能否降低最坏情况下的时间?