leetcode79丨单词搜索

这是一道简单的回溯题，正常dfs就能A，但是我做的时候内存爆了，从而发现了一个以前一直没发现的问题。

之前我只有需要对实参进行修改才会在定义函数时使用引用传递。这道题因为不用对字母表进行修改，所以我一开始直接传值：

bool dfs(vector<vector<char>> a,string word,int n,int x,int y)  // a为字母表，n为当前匹配长度，x、y为当前字母坐标

然后内存爆了。因为回溯题的数组一般都比较小，就算把整个数组直接传进去空间复杂度也才乘100左右，以前直接这样传内存一直没有爆过。以后递归的时候不能再这样传参了，太占空间了。

下面附上此题代码。

bool visit[16][16]={};  // 记录各字母是否被访问过
bool dfs(vector<vector<char>> &a,string word,int n,int x,int y){
    if (x>=a.size()||x<0||y>=a[0].size()||y<0) return false;  // 坐标越界
    if (visit[x][y]) return false;  // 已经用过的字母不能再次使用
    if (a[x][y]!=word[n]) return false;  // 字母不匹配
    if (n==word.length()-1) return true;  // 匹配成功
    visit[x][y]=1;  
    // 分别对上下左右四个方向进行搜索
    bool ans=dfs(a,word,n+1,x+1,y)||dfs(a,word,n+1,x-1,y)||dfs(a,word,n+1,x,y+1)||dfs(a,word,n+1,x,y-1);
    visit[x][y]=0;
    return ans;
}
bool exist(vector<vector<char>>& board, string word) {
    //分别以每个点为起点进行搜索
    for (int i=0;i<board.size();i++){
        for (int j=0;j<board[0].size();j++){
            if (dfs(board,word,0,i,j)) return true;
        }
    }
    return false;
}

这样就A了，就没有再剪枝了。。