1 条题解

  • 1
    @ 2026-3-18 19:17:34
    #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
    标签
    递交数
    17
    已通过
    7
    上传者