在網格中搜索一個詞

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 

開始，可以搜索字符串矩陣的行的功能：

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]; 

例如，這給出了在矩陣A水平字符串sh的（行，列）的位置：

>> 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 

總結與循環在所有方向/方向搜索得到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 

我希望這個作品。