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 =
[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCCED" , -> returns true , word = "SEE" , -> returns true , word = "ABCB" , -> returns false .
resursive DFS, 为了不用把board中的每一个元素都试一遍probe, 先将开头字母放在一个stack上，要探索就取stack顶部元素
之后，写一个helper function called probe, 把要探索的位置，board本身，word和word中字母的位置给传进去
probe中，首先判断传进来的位置是不是invalid，然后判断位置上的字母是不是word中对应位置的字母，然后判断是不是已经在找word中最后一个字母了（如果是的话，则不用进行下一步递归探寻，直接return true了）
在board上，把该位置元素改为空格，示意在当前探寻路线上，此元素已经visited，不可再用
接下来，进行下一步递归探寻，把当前元素的上下左右一次再用probe探寻一遍，如果没有返回false,说明找到了，可return true
class Solution { public: bool exist(vector<vector<char>>& board, string word) { int n = board.size(); int s = word.size(); stack<pair<int, int>> st; if (n == 0 || s == 0) return false; for (int i = 0; i < n; i++){ for (int j = 0; j < board[i].size(); j++){ if (board[i][j] == word[0]){ st.push(make_pair(i, j)); } } } while(!st.empty()){ int i = st.top().first; int j = st.top().second; if (probe(i, j, board, word, 0)) return true; else st.pop(); } return false; } bool probe(int i, int j, vector<vector<char>>& board, string word, int pos){ if (i<0 || j<0 || i>= board.size() || j>= board[0].size()) return false; if (board[i][j] != word.at(pos)) return false; if (pos == word.size()-1) return true; char tmp = board[i][j]; board[i][j] = ' '; if (probe(i+1, j, board, word, pos+1)){ return true; } if (probe(i-1, j, board, word, pos+1)){ return true; } if (probe(i, j+1, board, word, pos+1)){ return true; } if (probe(i, j-1, board, word, pos+1)){ return true; } board[i][j] = tmp; return false; } };
