深度优先搜索模板

基础模板 C++ 公开

#include <iostream>
using namespace std;
int mp[27][27];
int vis[27][27];  // 主函数外面的数组默认初始化为0
int dx[4] = {1, 0, -1, 0}; // 下 右 上 左
int dy[4] = {0, 1, 0, -1};
int n, m;
int ex, ey; // 终点坐标
bool flag = false;
void dfs(int x, int y){
    if (x == ex && y == ey){
        flag = true;
        return ;
    }
    for (int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >0 && nx<=n && ny>0 && ny<=m && vis[nx][ny]==0 && mp[nx][ny] == 0){
            vis[nx][ny] = 1;
            dfs(nx, ny);
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            cin >> mp[i][j];
        }
    }
    cin >> ex >> ey;
    vis[1][1] = 1; // 记录1，1这个位置我们已经走过了
    dfs(1, 1);
    if (flag) cout << "YES";
    else cout << "NO";
    return 0;
}