Поиск слова в сетке

Question

Я пытаюсь написать функцию, которая берет квадратную сетку букв и дает слово для поиска из списка слов, оно ищет ее по горизонтали, по вертикали или по диагонали (также смотрит назад в каждом случае). Я пробовал писать эту функцию по-разному без успеха, поэтому мне было интересно, как мой общий алгоритм звучит нормально и реализуемо.

• Возвращенные координаты для всюду по первой букве слова происходит так, что-то вроде [row,col] = find(grid==words(2)) со словами являются списком слов и сетками являются квадратной матрицей. Таким образом, это будет искать в пределах grid для второго слова в words.

• Для каждого случая этой буквы перемещение по вертикали, по горизонтали и по диагонали во всех направлениях по длине слова, а если последняя буква - буква последней буквы слова, мы ищем для хранения каждого символа от первого до последние как слова в массиве.

• Сравните каждое из этих слов с словом, которое мы ищем, и если есть спичка, нарисуйте линию.

Мысли?

Answer 1

Учитывая массив символов и вложенных строк, чтобы найти по горизонтали, вертикали, и оба диагональных направлениях:

A = char(randi(16,7,10)+'a'-1) 
A = 
    ilhpcdchkl 
    ooaecloocd 
    kogajcdkpg 
    imlnnbiihf 
    bigoahciin 
    afjfjdhgmp 
    pejcdfnmke

% horizontal string in row 4, starting at col 5 
cH = [4 5]; l = 4; % strings of length 4 
sh = A(cH(1),cH(2)+(0:l-1)) 
sh = 
    nbii 

% vertical string in col 6, starting at row 3 
cV = [2 6]; 
sv = A(cV(1)+(0:l-1),cV(2)).' %' 
sv = 
    lcbh 

% diagonal (downward) string starting at row 3, col 7 
cD = [3 7]; 
sd = A((cD(1)+(0:l-1))+size(A,1)*((cD(2)+(0:l-1))-1)) 
sd = 
    diip 

% diagonal (upward) string starting at row 5, col 2 
cU = [5 2] 
su = A((cU(1)-(0:l-1))+size(A,1)*((cU(2)+(0:l-1))-1)) 
su = 
    ilac 

Start с функцией, которая может искать строки матрицы для строки:

function ij = strsearch(A,s) 

C = mat2cell(A,ones(size(A,1),1),size(A,2)); 
matches = strfind(C,s); 
rows = find(~cellfun(@isempty,matches)); 
if ~isempty(rows), 
    cols = vertcat(matches{rows}); 
else 
    cols = []; 
end 
ij = [rows cols]; 

Например, это дает это (строка, столбец) расположение горизонтальной строки sh в матрице A:

>> ij = strsearch(A,sh) 
ij = 
    4  5 

Это отлично подходит для горизонтальных струн, но мы хотим, чтобы поиск во всех направлениях и направлениях. Мы новая функция, называем его wordsearch, что будет выводить следующее:

>> matches = wordsearch(A,sh) 
matches = 
      start: [4 5] 
    orientation: 'horizontal' 
     direction: 0 % forward 
>> matches = wordsearch(A,sv) 
matches = 
      start: [2 6] 
    orientation: 'vertical' 
     direction: 0 
>> matches = wordsearch(A,sd) 
matches = 
      start: [3 7] 
    orientation: 'downward diagonal' 
     direction: 0 
>> matches = wordsearch(A,su) 
matches = 
      start: [5 2] 
    orientation: 'upward diagonal' 
     direction: 0 
>> matches = wordsearch(A,fliplr(sh)) 
matches = 
      start: [4 8] % sh goes from column 5 to 8, in row 4 
    orientation: 'h' 
     direction: 1 % backward 

Чтобы получить это, мы можем построить на strsearch для поиска горизонтальных и вертикальных вхождений перестановки матрицы. Обратные вхождения можно найти, перевернув входную строку. Для поиска диагоналей мы можем использовать arrayfun и diag, чтобы извлечь диагонали и выполнить поиск аналогичным образом.

Общая функция поиска:

function ij = wordsearcher(A,s,orientation,order) 
s = s(:).'; %' ensure row vector 
if order, s = fliplr(s); end 
switch lower(orientation(1)) 
    case 'h' 
     ij = strsearch(A,s); 
     if order && ~isempty(ij), ij(:,2) = ij(:,2) + numel(s) - 1; end 
    case 'v' 
     ij = fliplr(strsearch(A.',s)); %' 
     if order && ~isempty(ij), ij(:,1) = ij(:,1) + numel(s) - 1; end 
    case 'd' % down-right diagonals 
     Cdiags = arrayfun(@(k)diag(A,k).',-size(A,1)+1:size(A,2)-1,'uni',0); %' 
     matches = strfind(Cdiags,s); 
     k = find(~cellfun(@isempty,matches)); 
     if isempty(k), ij=[]; return; end 
     row = (k<=size(A,1)) .* (size(A,1) - k) + [matches{k}]; 
     col = ~(k<=size(A,1)) .* (k - size(A,1)) + [matches{k}]; 
     ij = [row; col].'; %' 
     if order, ij = ij+numel(s)-1; end 
    case 'u' % up-right diagonals 
     Cdiags = arrayfun(@(k)diag(flipud(A),k).', ... %' flip A up-down 
              -size(A,1)+1:size(A,2)-1,'uni',0); 
     matches = strfind(Cdiags,s); 
     k = find(~cellfun(@isempty,matches)); 
     if isempty(k), ij=[]; return; end 
     row = ~(k<=size(A,1)) .* (size(A,1) - k) + k - [matches{k}] + 1; 
     col = ~(k<=size(A,1)) .* (k - size(A,1)) + [matches{k}]; 
     ij = [row; col].'; %' 
     if order, ij=bsxfun(@plus,ij,numel(s)*[-1 1]); end 
    otherwise 
     error('bad orientation') 
end 

Wrap, что с петлями для поиска во всех направлениях/направлениях, чтобы получить wordsearch функцию:

function matches = wordsearch(A,s) 
matches = struct('start',[],'orientation',[],'direction',[]); 
n=1; o='hvdu'; 
ostr = {'horizontal','vertical','downward diagonal','upward diagonal'}; 
for id=0:1, 
    for io=1:numel(o), 
     ij = wordsearcher(A,s,o(io),id); 
     if ~isempty(ij), 
      matches(n).start = ij; 
      matches(n).orientation = ostr{io}; 
      matches(n).direction = id; 
      n = n+1; 
     end 
    end 
end 

Я надеюсь, что это работает.