Pythonで単語がグリッドに存在するかどうかを確認します

単語のグリッドまたはマトリックスがあるとします。特定の単語がグリッドに存在するかどうかを確認する必要があります。単語は、水平方向に左右、垂直方向に上下の4つの方法で見つけることができます。単語が見つかった場合はTrueを返し、そうでない場合はFalseを返します。

したがって、入力が次のような場合

input_str ="python"の場合、出力はTrueになります。

これを解決するには、次の手順に従います-

• 関数find_grid（）を定義します。これは、matrix、input_str、row_pos、col_pos、row_count、col_count、degree
  を取ります。
  • 次数がinput_strのサイズと同じである場合、
    • Trueを返す
  • row_pos<0またはcol_pos<0またはrow_pos>=row_countまたはcol_pos>=col_countの場合、
    • Falseを返す
  • matrix [row_pos、col_pos]がinput_str [degree]と同じ場合、
    • temp：=matrix [row_pos、col_pos]
    • matrix [row_pos、col_pos]の要素を「＃」に置き換えます
    • result：=find_grid（matrix、input_str、row_pos-1、col_pos、
      • row_count、col_count、degree + 1）ビット単位または
      • find_grid（matrix、input_str、row_pos + 1、col_pos、row_count、
      • col_count、degree + 1）ビット単位または
      • find_grid（matrix、input_str、row_pos、col_pos-1、row_count、
      • col_count、degree + 1）ビット単位または
      • find_grid（matrix、input_str、row_pos、col_pos + 1、row_count、col_count、degree + 1））
    • matrix [row_pos、col_pos]の要素をtempに置き換えます
    • 結果を返す
  • それ以外の場合、
    • Falseを返す
• メインの関数/メソッドから、次の手順を実行します-
• input_strの長さが>row_count* col_countの場合、
  • Falseを返す
• 0からrow_countの範囲の行については、
  • 0からcol_countの範囲のcolの場合、do
    • matrix [row、col]がinput_str [0]と同じ場合、
      • if（find_grid（matrix、input_str、row、col、row_count、col_count、0）is True）、then
        • Trueを返す
• Falseを返す

例

理解を深めるために、次の実装を見てみましょう-

def find_grid(matrix, input_str, row_pos, col_pos, row_count, col_count, degree) :
   if (degree == len(input_str)) :
      return True
   if (row_pos < 0 or col_pos < 0 or row_pos >= row_count or col_pos >= col_count) :
      return Fals
   if (matrix[row_pos][col_pos] == input_str[degree]) :
      temp = matrix[row_pos][col_pos]
      matrix[row_pos].replace(matrix[row_pos][col_pos], "#")
      result = (find_grid(matrix, input_str, row_pos - 1, col_pos, row_count, col_count, degree + 1) |find_grid(matrix, input_str, row_pos + 1, col_pos, row_count, col_count, degree + 1) |find_grid(matrix, input_str, row_pos, col_pos - 1, row_count, col_count, degree + 1) |find_grid(matrix, input_str, row_pos, col_pos + 1, row_count, col_count, degree + 1))
      matrix[row_pos].replace(matrix[row_pos][col_pos], temp)
      return result
   else :
      return False
def solve(matrix, input_str, row_count, col_count) :
   if (len(input_str) > row_count * col_count) :
      return False
   for row in range(row_count) :
      for col in range(col_count) :
         if (matrix[row][col] == input_str[0]) :
            if (find_grid(matrix, input_str, row, col, row_count, col_count, 0)) :
               return True
   return False
word_grid = ["pghsf", "ykdgh", "tkghi", "hnsjs", "ojfgh", "nrtyu"]
print(solve(word_grid, "python", 6, 5))

入力

["pghsf", "ykdgh", "tkghi", "hnsjs", "ojfgh", "nrtyu"],"python"

出力

True