深度优先搜索（DFS）
因为dfs搜索是一个方向，并需要回溯，所以用递归的方式来实现，而有递归的地方就有回溯。
void dfs(参数) { if (终止条件) { 存放结果; return; } for (选择：本节点所连接的其他节点) { 处理节点; dfs(图，选择的节点); // 递归 回溯，撤销处理结果 } }
总体代码：
int dir[4][2] = {{0, 1}, // 右
{1, 0}, // 下
{-1, 0}, // 上
{0, -1}}; // 左
void dfs(const vector<vector<char>>& grid, vector<vector<bool>>& visited,
int x, int y) {
if (visited[x][y] || grid[x][y] == '0')
return;
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 ||
nexty >= grid[0].size()) {
continue;
}
dfs(grid, visited, nextx, nexty);
}
}
广度优先搜索(BFS)
广搜的搜索方式就适合于解决两个点之间的最短路径问题。
因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。
总体代码：
int dir[4][2] = {{0, 1}, // 右
{1, 0}, // 下
{-1, 0}, // 上
{0, -1}}; // 左
void bfs(const vector<vector<char>>& grid, vector<vector<bool>>& visited,
int x, int y) {
queue<pair<int, int>> que;
que.push({x, y});//起始节点加入队列
visited[x][y] = true; // 只要加入队列，立刻标记
while (!que.empty()) {
//从队列中取元素
pair<int, int> cur = que.front();
que.pop();
int curx = cur.first;
int cury = cur.second;
for (int i = 0; i < 4; i++) {
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 ||
nexty >= grid[0].size())
continue; // 越界了，直接跳过
if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') {
que.push({nextx, nexty});
visited[nextx][nexty] = true; // 只要加入队列立刻标记
}
}
}
}
暂无评论