在网格中搜索单词 [英] Searching for a word in a grid

问题描述

我正在尝试编写一个函数，该函数采用字母的正方形网格并给定一个单词以从单词列表中进行查找，它会沿水平，垂直或对角线(在每种情况下都向后看)进行搜索.我曾尝试过以各种方式编写此函数，但均未成功，所以想知道我的通用算法听起来是否可行且可实现.

I'm trying to write a function that takes a square grid of letters and given a word to find from a list of words, it searches for it horizontally, vertically or diagonally (also looking backwards in each case). I've tried writing this function in various ways with no success so was wondering if my general algorithm sounded ok and implementable.

• 返回单词首字母出现的所有位置的坐标，例如 [row,col] = find(grid==words(2))，其中单词是单词列表，而网格是方矩阵.因此，它将在grid中搜索words中的第二个单词.

• Return co-ordinates for everywhere the first letter of the word occurs so something like [row,col] = find(grid==words(2)) with words being the list of words and grid being the square matrix. So this would search within grid for the second word in words.

对于该字母的每次出现，都将在各个方向上沿垂直，水平和对角线移动该单词的长度；如果最后一个字母是该单词的最后一个字母，我们正在寻找从第一个字母到第一个字母的每个字符最后一个单词是数组中的单词.

For each occurrence of this letter move vertically, horizontally and diagonally in all directions for the length of the word and if last letter is that of the last letter of the word we are looking for store each character from first to the last as words in an array.

将这些单词中的每个单词与我们正在寻找的单词进行比较，如果有匹配项，请划一条线.

Compare each of these words to the word we are looking for and if there is a match draw a line.

有想法吗?

推荐答案

考虑字符数组和子字符串以沿水平，垂直和两个对角线方向查找:

Considering a character array and sub-strings to find along horizontal, vertical, and both diagonal directions:

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 with a function that can search the rows of a matrix for a string:

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中的(行，列)位置:

For example, this gives is the (row,column) location of the horizontal string sh in the matrix A:

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

这对水平字符串来说很棒，但是我们想要的是能够在所有方向和方向上搜索的功能.我们有一个新函数，称为wordsearch，它将输出以下内容:

That's great for horizontal strings, but what we want is the ability to search in all orientations and directions. We a new function, call it wordsearch, that will output the following:

>> 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提取对角线并以类似的方式进行搜索.

To get this, we can build on strsearch to search for horizontal and vertical occurrences by transposing the matrix. Backwards occurrences can be found by flipping the input string. To search diagonals, we can use arrayfun and diag to extract the diagonals and search in a similar manner.

常规搜索功能:

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

使用循环将其包裹起来，以在所有方向/方向进行搜索以获得wordsearch函数:

Wrap that with loops to search in all orientations/directions to get the wordsearch function:

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

我希望这行得通.

这篇关于在网格中搜索单词的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！