题解 | #牛群定位系统#

#include <iostream>
#include <ostream>
#include <vector>
#include <string>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board char字符型vector<vector<>>
     * @param words string字符串vector
     * @return string字符串vector
     */

    vector<pair<int,int>> v_p = {{-1,0},{1,0},{0,-1},{0,1}};
    vector<string> ans;

    void dfs(vector<vector<char> > board,vector<vector<bool> > flag, int i, int j, string target, int index, bool& t_falg)
    {
        if(index == target.size()-1 && !t_falg)
        {
            t_falg = true;
            return;
        }

        int m = board.size();
        int n = board[0].size();
        flag[i][j] = true;

        if(i<0 || i>=m || j<0 || j>=n)
            return;

        for(auto p:v_p)
        {
            int t_i = i + p.first;
            int t_j = j + p.second;
            if(t_i>=0 && t_i<m && t_j>=0 && t_j<n && board[t_i][t_j]==target[index+1] && !flag[t_i][t_j] && !t_falg)    
                dfs(board,flag,t_i,t_j,target,index+1,t_falg);
        }

        return;
    }

    vector<string> findWords(vector<vector<char> >& board, vector<string>& words) {
        // write code here
        // 三重遍历
        int m = board.size();
        int n = board[0].size();
        // 标记每个位置
        vector<vector<bool> > flag(m,vector<bool>(n,false));

        for(auto target:words)
        {
            bool t_falg = false;
            for(int i=0; i<m; ++i)
            {
                // 避免重复计算
                if(t_falg)
                    break;
                for(int j=0; j<n; ++j)
                {
                    if(board[i][j]==target[0])
                    {
                        dfs(board,flag,i,j,target,0,t_falg);
                        if(t_falg)
                        {
                            ans.emplace_back(target);
                            break;
                        }
                            
                    }
                }
            }
        }

        return ans;
    }
};