1 条题解
-
0
#include #include using namespace std;
int N, M, T; int sx, sy, fx, fy; int grid[6][6]; // 标记矩阵:0-可走且未访问,1-障碍,2-已访问 int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向 int count = 0; // 记录路径总数
void dfs(int x, int y) { // 若到达终点,路径数加1 if (x == fx && y == fy) { count++; return; }
// 尝试四个方向的移动 for (int i = 0; i < 4; i++) { int nx = x + dir[i][0]; int ny = y + dir[i][1]; // 检查新位置是否合法(在迷宫内、非障碍、未访问) if (nx >= 1 && nx <= N && ny >= 1 && ny <= M && grid[nx][ny] == 0) { grid[nx][ny] = 2; // 标记为已访问 dfs(nx, ny); // 递归探索 grid[nx][ny] = 0; // 回溯,取消标记 } }
}
int main() { cin >> N >> M >> T; cin >> sx >> sy >> fx >> fy;
// 初始化标记矩阵,所有位置初始为可走(0) memset(grid, 0, sizeof(grid)); // 标记障碍位置 for (int i = 0; i < T; i++) { int x, y; cin >> x >> y; grid[x][y] = 1; } // 标记起点为已访问 grid[sx][sy] = 2; // 从起点开始DFS dfs(sx, sy); // 输出路径总数 cout << count << endl; return 0;
}
- 1
信息
- ID
- 76
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- 递交数
- 39
- 已通过
- 18
- 上传者