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
    标签
    递交数
    16
    已通过
    7
    上传者