(dfs 单词搜索)leetcode 79

核心思路 用双重循环以所有的位置都作为起始点开始遍历

设置边界条件 上下左右都搜一次，不合适就回来，二叉树思想

经过的结点设置"#'避免重复搜索导致数据混乱

递归完后要还原原字符

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;


bool check = false;


void bracktracking(vector<vector<char>>& board, int x, int y, int x_m, int y_m, int len, int c, string word)
{




    if (check)
        return;
    if (x == x_m || x == -1)
        return;
    if (y == y_m || y == -1)
        return;
//非引用数组的边界条件放最前面，防止越界

    char m = board[x][y];//存储字符，用于还原

    if (board[x][y] == '#')
        return;
    
    
 
    
    if (board[x][y] != word[c])
        return;
    else
    {
        
        board[x][y] = '#';//标记已经过
        c++;
        if (c == len)
        {
            check = true;
        }
    }
    bracktracking(board, x, y + 1, x_m, y_m, len, c, word);
    bracktracking(board, x, y - 1, x_m, y_m, len, c, word);
    bracktracking(board, x+1, y, x_m, y_m, len, c,word);
    
    bracktracking(board, x-1, y , x_m, y_m, len, c, word);
    board[x][y] = m;//还原字符

}

bool exist(vector<vector<char>>& board, string word) {
    
    
    for (int i = 0;i < board.size();i++)
    {
        for (int j = 0;j < board[i].size();j++)
        {
            bracktracking(board, i, j,board.size(),board[i].size(),word.size(),0,word);
        }
   }


    return check;
}

int main()
{
    std::vector<std::string> strs = { "ABCE", "SFCS", "ADEE" };
    std::vector<std::vector<char>> board;

    for (const auto& str : strs) {
        std::vector<char> row(str.begin(), str.end());
        board.push_back(row);
    }

    string word = "SEE";
    if (exist(board, word))
        cout << "找到了";
    else
        cout << "没找到";
   
    
    
    cout << endl;
    for (auto n : board)
    {
        for (int i = 0;i < n.size();i++)
            cout << n[i]<<" ";
        cout << endl;
    }

	return 0;
}