DFS搜索算法中方向数组的含义及例题

方向数组含义

方向数组，常应用于搜索算法中，有四方向（上，右，下，左），也有八方向（顺时针或逆时针）。广泛应用于迷宫，棋盘等寻路问题中

方向数组解析

四方向

c代表示码：

dx[4] = {-1, 0, 1, 0}
dy[4] = {0, 1, 0, -1}

（-1，0）代表的是下，（0，1）代表的是向右，（1，0）代表向下，（0，-1）代表向左，寻路的时候可以顺时针选择任意下一个方向

图示：

八方向

c代表示码：

int dx[8] = {-1,  0,  1, 1, 1, 0, -1, -1};
int dy[8] = {-1, -1, -1, 0, 1, 1,  1,  0};

与四方向类似，只不过多加了四个斜方向

图示：

例题 单词搜索

题目链接

https://leetcode.cn/problems/word-search/

思路

在每个点都往四个方向搜索，查找目标单词，每次遍历过的要做好标记

AC代码

class Solution {
public:
    int n, m;
    vector<vector<char>> visited; // 记录已经访问过的点
    int dx[4] = &#123;-1, 0, 1, 0&#125;, dy[4] = &#123;0, 1, 0, -1&#125;;

    bool exist(vector<vector<char>>& board, string word) &#123;
        n = board.size(); // 行数
        m = board[0].size(); // 列数

        visited = vector<vector<char>> (n, vector<char>(m));
        for (int i = 0; i < n; i ++ )&#123;
            for (int j = 0; j < m; j ++ )&#123;
                if (dfs(board, word, 0, i, j)) return true; // 搜索到了
            &#125;
        &#125;
        return false;
    &#125;

    bool dfs(vector<vector<char>> &board, string &word, int u, int x, int y)&#123;
        if (board[x][y] != word[u]) return false; // 不匹配
        if (u == word.size() - 1) return true; // 找得到

        visited[x][y] = true;
        // 查看四个方向
        for (int i = 0; i < 4; i ++ )&#123;
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny]) continue; // 判断边界
            if (dfs(board, word, u + 1, nx, ny)) return true;
        &#125;
        visited[x][y] = false; // 恢复现场
        return false;
    &#125;

&#125;;