Untitled
python
a month ago
2.1 kB
1
Indexable
Never
board = """ DNG IO0 HMB """ board = [list(item) for item in board.split()] def get_word(pos, board): return board[pos[0]][pos[1]] def replace_str_index(text,index=0,replacement=''): return '%s%s%s'%(text[:index],replacement,text[index+1:]) def get_move(pos, board): moves = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]] col_len = len(board) row_len = len(board[0]) res = [] for move in moves: col_pos = move[0] + pos[0] row_pos = move[1] + pos[1] if 0 > col_pos or col_pos > col_len - 1 or 0 > row_pos or row_pos > row_len - 1 or board[col_pos][row_pos] == '0': continue res.append([col_pos, row_pos]) return res def copy_board(board): return [item.copy() for item in board] def dynamic_board(pos, board, step): queue = [] word = board[pos[0]][pos[1]] queue.append([word, copy_board(board), pos]) res = set([]) while queue: cur_word, cur_board, cur_pos = queue.pop(0) if len(cur_word) == step: res.add(cur_word) continue moves = get_move(cur_pos, cur_board) cur_board[cur_pos[0]][cur_pos[1]] = '0' for move in moves: new_word = cur_word + get_word(move, cur_board) new_board = copy_board(cur_board) new_board[move[0]][move[1]] = '0' queue.append([new_word, new_board, move]) return res def find_indices(list_to_check, item_to_find): return [idx for idx, value in enumerate(list_to_check) if value == item_to_find] def solve(word, board, step): word = word.upper() res = set([]) for row in range(len(board)): idx = find_indices(board[row], word) word_pos = [] for item in idx: word_pos.append([row, item]) for pos in word_pos: res |= dynamic_board(pos, board, step) for item in res: print(item) solve('D', board, 3)