# Code Clash 2019
# Problem 8: Search
# https://www.codeclash.org
# Parse input
wordCount, heightCount = map(int, input().split())
words = []
board = []
for i in range(wordCount):
words.append(input())
for i in range(heightCount):
board.append(input())
# Remove the spaces between letters
board = [row.replace(' ', '') for row in board]
# Search for a word horizontally
def search_horizontal(word, board):
# Go through each row
for r in range(len(board)):
# Search the row for the word
search = board[r].find(word)
if search != -1:
# Add the word indices to an array
locations = []
for i in range(len(word)):
locations.append((r, search + i))
return locations
# Word not found
return []
# Search the diagonal to the left for a word
def search_left_diagonal(word, board):
# Compute the center of the board
center_row = len(board) // 2
# Keep track of the maximum depth of the diagonal
max_depth = 0
# Identify the start of the diagonals
for starting_row in range(center_row, len(board)):
# Search through each letter of the diagonal for the word
depth = 0
locations = []
current_search_idx = 0
for r in range(starting_row, -1, -1):
# If the row has enough letters to search
if (len(board[r]) >= (depth + 1)):
current_letter = board[r][depth]
# Check if the letter is a part of the word
if current_letter == word[current_search_idx]:
# Keep track of the indices
locations.append((r, depth))
current_search_idx += 1
if current_search_idx == len(word):
return locations
else:
# Restart the search
locations.clear()
current_search_idx = 0
# Increase the depth of the diagonal within the next row
depth += 1
depth = min(depth, max_depth)
# The diagonals are moving further to the right
max_depth += 1
# Nothing found
return []
# Search for diagonals going to the right
def search_right_diagonal(word, board):
# Compute the center of the board
center_row = len(board) // 2
# Keep track of the maximum depth of the diagonal
max_depth = 0
# Identify the start of the diagonals
for starting_row in range(0, center_row + 1):
# Search through each letter of the diagonal for the word
depth = 0
locations = []
current_search_idx = 0
for r in range(starting_row, len(board)):
# If the row has enough letters to search
if (len(board[r]) >= (depth + 1)):
current_letter = board[r][depth]
# Check if the letter is a part of the word
if current_letter == word[current_search_idx]:
# Keep track of the indices
locations.append((r, depth))
current_search_idx += 1
if current_search_idx == len(word):
return locations
else:
# Restart the search
locations.clear()
current_search_idx = 0
# Increase the depth of the diagonal within the next row
depth += 1
depth = min(depth, max_depth)
# The diagonals are moving further to the right
max_depth += 1
# Nothing found
return []
# Keep track of the found words
found = []
# Find words in horizontal forward direction
for word in words:
locations = search_horizontal(word, board)
if len(locations) != 0:
found.append((word, locations))
# Find words in horizontal backward direction
for word in words:
# The word[::-1] is shorthand for reversing a string
locations = search_horizontal(word[::-1], board)
if len(locations) != 0:
found.append((word, locations))
# Find words in left diagonal (forward)
for word in words:
locations = search_left_diagonal(word, board)
if len(locations) != 0:
found.append((word, locations))
# Find words in left diagonal (backward)
for word in words:
locations = search_left_diagonal(word[::-1], board)
if len(locations) != 0:
found.append((word, locations))
# Find words in right diagonal (forward)
for word in words:
locations = search_right_diagonal(word, board)
if len(locations) != 0:
found.append((word, locations))
# Find words in right diagonal (backward)
for word in words:
locations = search_right_diagonal(word[::-1], board)
if len(locations) != 0:
found.append((word, locations))
# Keep track of all the locations containing the words
saved_locations = []
for word in found:
locations = word[1]
for location in locations:
saved_locations.append(location)
# Print out the final board
for r in range(len(board)):
print_str = ''
for c in range(len(board[r])):
if (r, c) not in saved_locations:
print_str += '- '
else:
print_str += board[r][c] + ' '
print(print_str[:len(print_str)-1])