###### tags: `Leetcode` `medium` `backtracking` `python` `Top 100 Liked Questions`

# 79. Word Search

## [題目連結:] https://leetcode.com/problems/word-search/

## 題目:
Given an ```m x n``` grid of characters ```board``` and a string ```word```, return true if ```word``` exists in the grid.

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


#### [圖片來源:]https://leetcode.com/problems/word-search/

## 解題想法:
* 題目為找word是否出現於board中
* 解法:
* 額外創建個size等於board，全為true的matrix_flag用以紀錄是否拜訪過該位置
* flag = [[True] * n for _ in range(m)]
* 遍歷board每格，若該位置board[i][j]==word[0]
* 標記該位置flag[i][j]=False
* 跑**dfs**
* 若後續字也都可以正確找到，return True
* 否則，將flag[i][j]改回True，給後面的人嘗試
* dfs:
* input:
* cur_x,cur_y為當前位置
* cur_pos為當前遍歷到的字母長度
* output:
* return True if 可以找到整組字串 else False
* 函式內部:
* 終止條件:
* cur_pos==len(word)
* 遍歷上下左右四個方向:
* 判斷新位置是否在邊界範圍內
* 且尚未走過
* 且為正確的字母
* 標記該新位置flag為False走過
* 再次遞迴找下個位置
* 若後續字也都可以正確找到，return True
* 否則，將flag[i][j]改回True，給後面的人嘗試

## Python:

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        #x,y為當前位置 cur_pos為當前遍歷到的字母長度
        #返回為是否能找到
        def dfs(curX,curY,curPos):
            if curPos==len(word):
                return True
            dirs= [[1,0],[-1,0],[0,1],[0,-1]]
            #遍歷上下左右
            for dirX,dirY in dirs:
                tmpX=curX+dirX
                tmpY=curY+dirY
                #判斷是否在界內 且 沒拜訪過 且為正確的字母
                if 0<=tmpX<m and 0<=tmpY<n and flag[tmpX][tmpY]==True and board[tmpX][tmpY]==word[curPos]:
                    flag[tmpX][tmpY]=False #先設為已經拜訪
                    if dfs(tmpX,tmpY,curPos+1): #遞迴找下個字
                        return True
                    flag[tmpX][tmpY]=True
            return False
    
        m=len(board)
        n=len(board[0])
        #創建全為true的flag用以紀錄是否拜訪過該位置
        flag=[[True for _ in range(n)] for _ in range(m)]
        #遍歷board每個位置
        for i in range(m):
            for j in range(n):
                if board[i][j]==word[0]:
                    flag[i][j]=False
                    #開始位置(i,j)已符合長度(位置)1
                    if dfs(i,j,1):
                        return True
                    flag[i][j]=True 
                    #以(i,j)為起點找不到word
                    #但也許(i,j)可以做為word的中間內容，
                    #改回True給別人嘗試的機會
        return False
    
result = Solution()
board = [["C","A","A"],["A","A","A"],["B","C","D"]]
word = "AAB"
ans = result.exist(board,word)
print(ans)