1 条题解
-
1
#include<bits/stdc++.h> using namespace std; int n, m, ans = 1e9, vis[30][30]; int dx[] = {0, 0, 1,-1}, dy[] = {1,-1, 0, 0}; int sx, sy, ex, ey; char c[30][30]; //我们当前在(x,y)这个点,并且已经走了step步 void dfs(int x, int y, int step){ if(step>ans) return ; if (x == ex && y == ey){ ans = min(ans, step); return; } for (int i = 0; i < 4; i++){//遍历四个方向 int nx = x + dx[i], ny = y + dy[i]; if (nx >= 1 && nx<= n && ny>= 1 && ny <= m && vis[nx][ny] == 0 && c[nx][ny] != '#'){ vis[nx][ny] = 1; dfs(nx, ny, step + 1 + (c[nx][ny] == 'x')); vis[nx][ny] = 0; } } } int main(){ cin >> n >> m; for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++){ cin >> c[i][j]; if (c[i][j] == 'r') sx = i, sy = j; if (c[i][j] == 'a') ex = i, ey = j; } } vis[sx][sy] = 1; dfs(sx, sy, 0); if (ans == 1e9) cout << "Impossible"; else cout << ans; return 0; }
- 1
信息
- ID
- 5301
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 3
- 标签
- 递交数
- 16
- 已通过
- 7
- 上传者