[数据结构与算法]leetcode 79单词搜索

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
    //row
        for(int i = 0; i < board.size(); i++)
        //col
            for(int j = 0; j < board[i].size(); j++)
            //从word下标为0开始遍历
                if(dfs(board,word,0,i,j)) return true;
        return false;        
    }
    //方向数组，数字只有上下左右相邻位置
    int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1}; 
    bool dfs(vector<vector<char>>& board, string& word,int u,int x,int y)
    {
    //递归终止的条件
        if(board[x][y] != word[u]) return false;
        //就说明目标的下标遍历完了，找到了
        if(u == word.size() - 1)   return true;
        //防止重复遍历，用符号.覆盖遍历的位置
        char t = board[x][y];
        board[x][y] = '.';
        //4个方向
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            //出界或者走到已经搜索过的位置
            if(a < 0 || a >= board.size() || b < 0 || b >= board[0].size() || board[a][b] == '.') {
                continue;
            } 
            //word下标增加
            if(dfs(board,word,u+1,a,b)) return true;
        }
        board[x][y] = t;
        return false;
    }
};

这个用C++写的，说实话我感觉刷题的时候我就是个废物，别人的脑子为什么那么聪明，这个也是看别人的思路理解清楚的，算了，勤能补拙。
这个主要是用了深度优先搜索，什么是深度优先搜索那？
深度优先搜索（缩写DFS）有点类似广度优先搜索，也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。

在这里我还搞懂了一个为什么需要引用的问题，引用在使用的时候必须初始化，但是引用作为函数参数的时候，不需要像指针作为形参一样开辟空间，如果直接传变量，形参和实参的存储位置是不一样的，所以在简单的交换值的程序中无法交换。