深搜(dfs)和广搜(bfs)

• 广搜可以用来解决最小路径问题和连通性问题
• 深搜可以解决连通性问题

实现方式

• 深搜用函数递归实现
• 广搜用队列实现

问题

输入地图判断连通性和最小路径，每次只能走上下左右，S为起点，T为终点，#为障碍物，.可以走，如以下地图：

S…

###…

…

.###.

…T.

• 深搜代码如下

#include <iostream>
using namespace std;
int n, m, sx, sy;
char mmap[105][105];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int func(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if (mmap[xx][yy] == 'T')
            return 1;
        if (mmap[xx][yy] == '.') {
            mmap[xx][yy] = 0;
            if (func(xx, yy) == 1)
                return 1;
        }
    }
    return 0;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
    		cin >> mmap[i][j];
            if (mma[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    }
    if (func(sx, sy) == 1) 
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

• 广搜代码如下：

#include <iostream>
#include <queue>
using namespace std;
int n, m, sx, sy;
char mmap;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
struct node {
    int x, y, step;
};
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mmap[i][j];
            if (mmap[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    }
    queue<node> que;
    que.push((node){sx, sy, 0});
    while (!que.empty()) {
        node temp = que.front();
        que.pop();
        for (int i = 0; i < 4; i++) {
            int x = temp.x + dir[i][0];
            int y = temp.y + dir[i][1];
            if (mmap[x][y] == 'T') {
                cout << temp.step + 1 << endl;
                return 0;
            }
            if (mmap[x][y] == '.') {
                mmap[x][y] = 0;
                que.push((node){x, y, temp.step + 1});
            }
        }
    }
    cout << "No" << endl;
    return 0;
}