P1605 迷宫

# 迷宫都是经典DFS（BFS）题。我们需要模拟人走迷宫的一个过程，所以限制条件很好判断: ### 1：超出迷宫范围就要返回 ### 2：碰到墙就返回 ### 3：上下左右都走不通返回 ### 4：不能走前面已经走过的路 ~~那就死循环了~~ ------------ 代码如下 ```cpp #include <bits/stdc++.h> using namespace std; int n, m, t, sx, sy, ex, ey, times; int mapp[10][10]; // 存迷宫 bool v[10][10]; // 判断有没有走过 int ne[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; // 四个方向，一定要看清写对，好多次这里-1，1，0写错但没有发现，很难受。 void dfs(int x, int y); int main() { cin >> n >> m >> t; cin >> sx >> sy >> ex >> ey; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) mapp[i][j] = 1; } // 初始化迷宫为1，迷宫以外的多余地方为0，这样判断mapp[x][y]是否为0就可以判断是否出界 while (t--) { int x, y; cin >> x >> y; mapp[x][y] = 0; // 把有墙的地方变0 } dfs(sx, sy); cout << times << endl; return 0; } void dfs(int x, int y) { if (x == ex && y == ey) // 到达终点 { times++; return ; } //if (v[x][y] || mapp[x][y] == 0) return ; // 不能在这里判断，要在for循环里面就判断，这样会出界 for (int i = 0; i <= 3; ++i) { int xx = x + ne[i][0], yy = y + ne[i][1]; if (!v[xx][yy] && mapp[xx][yy] == 1) // 在这里判断可以预防出界 { v[x][y] = true; // 如果可以走(xx, xy)则在当前位置打标记，说明已经走过，避免死循环 // cout << x << " " << y << endl; dfs(xx, yy); v[x][y] = false; // 返回后要去除标记 } } return ; } ```