Рассмотрим:
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 выполняет работу, выполняет отслеживание в обратном направлении.
Есть ли лучший способ? или можно снизить время наихудшего случая?