8 条题解
-
0
// https://dashoj.com/p/84 // 1 可走 0 不可走 #include <bits/stdc++.h> #define N 20 using namespace std; typedef long long ll; int n, m; int ax, ay, bx, by; int g[N][N]; bool gb[N][N]; int dx[4] = {0, -1, 0, 1}; int dy[4] = {-1, 0, 1, 0}; vector<pair<int, int>> vp; bool b = false; void dfs(int x, int y) { if (x == bx && y == by) { // 到达终点 b = true; for (int i = 0; i < vp.size() - 1; i++) { cout << '(' << vp[i].first << ',' << vp[i].second << ")->"; } cout << '(' << x << ',' << y << ")" << endl; return; } for (int i = 0; i < 4; i++) { // 四个方向 int vx = x + dx[i], vy = y + dy[i]; // 走方格 if (vx >= 1 && vy >= 1 && vx <= n && vy <= m) { // 出界 if (g[vx][vy] && gb[vx][vy]) { // gb[vx][vy] = false; vp.push_back({vx, vy}); dfs(vx, vy); vp.pop_back(); gb[vx][vy] = true; } } } } int main() { fill(&gb[0][0], &gb[0][0] + N * N, true); ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> g[i][j]; } } cin >> ax >> ay; cin >> bx >> by; gb[ax][ay] = false; vp.push_back({ax, ay}); dfs(ax, ay); if (!b) { cout << -1 << endl; } return 0; }
信息
- ID
- 84
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 814
- 已通过
- 124
- 上传者