leetcode 79. 单词搜索

Description

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search

思考和编码过程
这一题本质上是路径搜索的题目，要用回溯。问题是怎么搜快一点。一开始想着通过一些预处理加快搜索。想了以下也没想出个什么。一开始写代码时，预处理了一个init数组，类型是unordered_map<char, vector<pair<int,int>> 用来存储每一种字符在地图上有哪些坐标相对应。可是写到后面搜索的时候发现也没啥子用，但是写的过程中倒是试着用了下move以及make_pair. 然后就是开始写搜索。写的过程中，一开始没考虑好递归结束条件，对于单个字母的特例程序出错。然后就是方向数组没写好。之后又发现忘了个条件，没有设置vis数组。然后代码写这样的。

class Solution {
public:
    unordered_map<char,vector<pair<int,int>>> init;

    int dr[4]={0,0,-1,1}, dc[4]={1,-1,0,0};
    int m,n;

    bool Invalid(int r,int c,vector<vector<char>>& board,vector<vector<int>> & vis){
        return r>=0&&r<m&&c>=0&&c<n&&!vis[r][c];
    }

    bool DFS(int r,int c,int d,string & word, vector<vector<char>>& board,vector<vector<int>> & vis){
        if(d>=word.length()) return true;
        if(board[r][c]!=word[d]) return false;
        if(d==word.length()-1) return true;
        for(int i=0;i<4;++i){
            int rr=r+dr[i],cc=c+dc[i];
            if(Invalid(rr,cc,board,vis)){
                vis[rr][cc]=1;
                if(DFS(rr,cc,d+1,word,board,vis)) return true;
                vis[rr][cc]=0;
            }
        }
        return false;
    }

    bool exist(vector<vector<char>>& board, string word) {
        m=board.size();
        n=board[0].size();
        for(int i=0;i<board.size();++i)
            for(int j=0;j<board[i].size();++j){
                char & ch=board[i][j];
                if(init.count(ch)){
                    init[ch].emplace_back(make_pair(i,j));
                }
                else{
                    vector<pair<int,int>> tmp;
                    tmp.emplace_back(make_pair(i,j));
                    init[ch]=move(tmp);
                }
        }

        char & ch=word[0];
        vector<vector<int>> vis(m);
        for(auto & it:vis) it.resize(n);
        for(auto & it:init[ch]){
            vis[it.first][it.second]=1;
            if(DFS(it.first,it.second,0,word,board,vis)) return true;
            vis[it.first][it.second]=0;
        }
        return false;
    }

};

看过题解的代码后学到的是，这样的初始化方式
vector<vector<int>> visited(h, vector<int>(w));
vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
还有就是vscode里移动到行首行尾用 home 和 end 键
直接编辑下一行用crtl+enter