class Vertex(object):

self.visited = False

def get_cell_key(i, j, M, N):

return i*N+j

def get_adjacent_cells(i, j, M, N):

adj = [(i+1, j), (i+1, j-1), (i, j-1), (i-1, j-1), (i-1, j), (i-1, j+1), (i, j+1), (i+1, j+1)]

return [(x, y) for x, y in adj if 0 <= x <= M-1 and 0 <= y <= N-1]

def add_vertex(key, vertices):

if not vertices.get(key):

vertices[key] = Vertex(key)

return vertices[key]

def build_graph(board):

return vertices

def is_word(w, dictionary):

''' Naive implementation. A better solution would use a trie. '''

return w in dictionary

def dfs(u, vertices, board, dictionary, stack, res):

u.visited = False

def solution(dictionary, board):

return res

if __name__ == '__main__':

import doctest

doctest.testmod()