4 条题解
-
1
using namespace std; const int MAXN = 20; int n, m; int maze[MAXN][MAXN]; bool visited[MAXN][MAXN]; int sx, sy, ex, ey; // 方向顺序:左、上、右、下 int dx[] = {0, -1, 0, 1}; int dy[] = {-1, 0, 1, 0}; // 路径存储 int pathX[MAXN * MAXN]; int pathY[MAXN * MAXN]; int pathLen; bool found; void dfs(int x, int y) { // 到达终点 if (x == ex && y == ey) { found = true; for (int i = 0; i < pathLen; i++) { if (i > 0) cout << "->"; cout << "(" << pathX[i] << "," << pathY[i] << ")"; } cout << endl; return; } // 按 左、上、右、下 顺序拓展 for (int d = 0; d < 4; d++) { int nx = x + dx[d]; int ny = y + dy[d]; // 边界检查 if (nx < 1 || nx > n || ny < 1 || ny > m) continue; // 可走且未访问 if (maze[nx][ny] == 1 && !visited[nx][ny]) { visited[nx][ny] = true; pathX[pathLen] = nx; pathY[pathLen] = ny; pathLen++; dfs(nx, ny); pathLen--; visited[nx][ny] = false; } } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> maze[i][j]; } } cin >> sx >> sy; cin >> ex >> ey; // 初始化 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) visited[i][j] = false; found = false; pathLen = 0; // 起点加入路径 visited[sx][sy] = true; pathX[pathLen] = sx; pathY[pathLen] = sy; pathLen++; dfs(sx, sy); if (!found) { cout << -1 << endl; } return 0; }
信息
- ID
- 1303
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 261
- 已通过
- 66
- 上传者