C++ dfs Backtracking


  • 0
    D

    c++ dfs backtracking

    '''
    class Solution {
    public:
    vector<vector<bool>> vis;
    int n;
    int m;
    bool flag = false;
    int dir[4][2] = {{0, -1},{0, 1}, {-1, 0}, {1, 0}};
    bool test(int x, int y)
    {
    if (x < 0 || x >= n || y < 0 || y >= m)
    return false;
    return true;
    }
    void dfs(vector<vector<char>>& v, string s, int x, int y, int pos)
    {
    if (flag)
    return ;
    if (pos == s.size())
    {
    flag = 1;
    return ;
    }

        vis[x][y] = true;
        for (int i = 0; i < 4; i++)
        {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if (test(dx, dy) && vis[dx][dy] == false && s[pos] == v[dx][dy])
                dfs(v, s, dx, dy, pos + 1);
        }
        vis[x][y] = false;
        
    }
    bool exist(vector<vector<char>>& board, string word) {
        if (word.empty())
            return true;
        if (board.empty())
            return false;
            
        n = board.size();
        m = board[0].size();
        vis.resize(n, vector<bool>(m, false));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (board[i][j] == word[0])
                    dfs(board, word, i, j, 1);
            }
        }
        
        return flag;
    }
    

    '''
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.