原题地址：https://oj.leetcode.com/problems/word-search/

题意：

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,

Given board =

[  ["ABCE"],  ["SFCS"],  ["ADEE"]]

word = "ABCCED", -> returns true,

word = "SEE", -> returns true,

word = "ABCB", -> returns false.

解题思路：使用dfs来搜索，为了避免已经用到的字母被重复搜索，将已经用到的字母临时替换为'#'就可以了。不知道用bfs可行否。

代码：

class Solution:    # @param board, a list of lists of 1 length string    # @param word, a string    # @return a boolean    def exist(self, board, word):        def dfs(x, y, word):            if len(word)==0: return True            #up            if x>0 and board[x-1][y]==word[0]:                tmp=board[x][y]; board[x][y]='#'                if dfs(x-1,y,word[1:]):                    return True                board[x][y]=tmp            #down            if x
     
      0 and board[x][y-1]==word[0]:                tmp=board[x][y]; board[x][y]='#'                if dfs(x,y-1,word[1:]):                    return True                board[x][y]=tmp            #right            if y