Python에 단어가 그리드에 있는지 여부 확인

그리드 또는 단어 행렬이 있다고 가정합니다. 주어진 단어가 그리드에 있는지 여부를 확인해야 합니다. 단어는 가로 좌우, 세로 상하의 4가지 방법으로 찾을 수 있습니다. 단어를 찾을 수 있으면 True, 그렇지 않으면 False를 반환합니다.

따라서 입력이 다음과 같으면

input_str ="python"이면 출력이 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• find_grid() 함수를 정의합니다. 이것은 행렬, input_str, row_pos, col_pos, row_count, col_count, degree
  를 취합니다.
  • 도가 input_str의 크기와 같으면
    • 참 반환
  • row_pos <0 또는 col_pos <0 또는 row_pos>=row_count 또는 col_pos>=col_count이면
    • 거짓을 반환
  • 행렬[row_pos, col_pos]이 input_str[도]와 같으면
    • temp :=행렬[row_pos, col_pos]
    • 매트릭스[row_pos, col_pos]의 요소를 '#'로 교체
    • 결과:=find_grid(행렬, input_str, row_pos - 1, col_pos,
      • row_count, col_count, degree + 1) 비트 또는
      • find_grid(행렬, input_str, row_pos + 1, col_pos, row_count,
      • col_count, 차수 + 1) 비트 또는
      • find_grid(행렬, input_str, row_pos, col_pos - 1, row_count,
      • col_count, 차수 + 1) 비트 또는
      • find_grid(행렬, input_str, row_pos, col_pos + 1, row_count, col_count, degree + 1))
    • 매트릭스[row_pos, col_pos]의 요소를 temp로 교체
    • 반환 결과
  • 그렇지 않으면
    • 거짓을 반환
• 주요 함수/메서드에서 다음을 수행합니다. -
• input_str의 길이> row_count * col_count이면
  • 거짓을 반환
• 0에서 row_count 범위의 행에 대해 다음을 수행합니다.
  • 0에서 col_count 범위의 col에 대해 다음을 수행합니다.
    • 행렬[row, col]이 input_str[0]과 같으면
      • if (find_grid(matrix, input_str, row, col, row_count, col_count, 0)가 True)이면
        • 참 반환
• 거짓을 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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