My question is motivated from a leetcode:

https://leetcode.com/problems/shortest-path-in-binary-matrix/

Given an n x n binary matrix grid with 1/0, return the shortest path that is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that: All the visited cells of the path are 0. All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

Obviously we will use queue for BFS:

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    if (grid[0][0] == 1) return -1;
    int res = 0, n = grid.size(), m = grid[0].size();
    vector<vector<int>> visited(n, vector<int>(m, 0));
    visited[0][0] = 1;
    queue<vector<int>> q;
    q.push({ 0, 0 });
    vector<vector<int>> dirs{ {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };
    while (!q.empty()) {
          res;
        for (int i = q.size(); i > 0; --i) {
            auto t = q.front(); q.pop();
            if (t[0] == n - 1 && t[1] == n - 1) return res;
            for (auto dir : dirs) {
                int x = t[0]   dir[0], y = t[1]   dir[1];
                if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 1 || visited[x][y]) continue;
                visited[x][y] = 1; 
                q.push({ x, y });
            }
        }
    }
    return -1;
}

My question is can BFS only solve the shortest path? For example to find all the available paths, then above BFS will not work since here we mark all the visited cells to avoid duplicate visits, which guarantees the result is shortest path. And usually we use recursion to find all available paths.

Here is using BFS to search all paths:

Update:

vector<vector<vector<int>>> fun2(vector<vector<int>> grid, int x, int y)
{
    vector<vector<vector<int>>> res;
    if (grid[x][y] == 1) return res;
    int n = grid.size(), m = grid[0].size();
    queue<vector<vector<int>>> q;
    q.push({ { x, y } });
    vector<vector<int>> dirs{ {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };
    while (!q.empty()) {
        for (int i = q.size(); i > 0; --i) {
            auto t = q.front(); q.pop();
            unordered_set<string> st;
            for (auto &it : t) st.insert(to_string(it[0])   ','   to_string(it[1]));
            int xx = t.back()[0], yy = t.back()[1];
            if (grid[xx][yy] == 2) res.push_back(t);
            for (auto dir : dirs) {
                int x = xx   dir[0], y = yy   dir[1];
                if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 1 || st.count(to_string(x)   ','   to_string(y))) continue;
                auto tem = t;
                tem.push_back({ x, y });
                q.push(tem);
            }
        }
    }
    return res;
}

CodePudding user response：

BFS could be used also to find all paths, but then it should not have a visited structure that is shared by all paths, but a separate structure for each path.

So instead of putting a single cell's coordinate on the queue, you'd put a path on the queue (consisting of coordinates of the cells on the path), and extend those paths with a next node when that node did not yet occur in that path.

As you can see that will require a lot more memory than DFS would need, without any clear compensating benefit.