1 条题解

  • 0
    @ 2026-1-27 22:53:46
    #include<bits/stdc++.h>
    using namespace std;
    
    // [1] n-迷阵的行数,m-迷阵的列数(全程使用0-based数组坐标)
    int n,m;
    // [2] arr数组-存储迷阵地图,字符含义:@起点、.可通行区域、*终点、#不可通行障碍
    char arr[100][100];
    // [3] dp数组-存储各坐标到起点的累计步数,初始化为INT_MAX表示「暂未访问/不可达」
    int dp[100][100];
    // [4] 四个方向偏移量(左、下、右、上),覆盖所有可移动的相邻方向
    int dx[4]={0,1,0,-1};
    int dy[4]={-1,0,1,0};
    // [5] a,b-起点@的0-based坐标;c,d-终点*的0-based坐标
    int a,b,c,d;
    
    // [6] DFS递归函数:从当前坐标出发遍历所有可达路径,更新各点到起点的步数
    // 参数说明:x-当前位置横坐标 | y-当前位置纵坐标 | len-从起点到当前位置的累计步数
    void dfs(int x,int y,int len){
    	// [7] 记录当前坐标的步数,更新为从起点到此处的累计步数
    	dp[x][y]=len;//把符合条件的数据存入dp中
    	// [8] 递归终止条件:到达终点*,直接返回(不再继续探索后续路径)
    	if(x==c && y==d) return;
    
    	// [9] 遍历四个方向,尝试向相邻位置扩展路径
    	for(int i=0;i<4;i++){
    		// [10] 计算相邻位置的横坐标和纵坐标
    		int tx=x+dx[i];
    		int ty=y+dy[i];
    		// [11] 路径合法性综合判断,满足所有条件才继续递归:
    		// (1) 坐标在迷阵合法范围内 (2) 相邻位置是可通行区域(.普通区域/*终点) (3) 新路径步数更短(剪枝,避免无效递归和重复更新)
    		if((tx>=0 && tx<n) && (ty>=0 && ty<m) && (arr[tx][ty]=='.' || arr[tx][ty]=='*') && len+1 < dp[tx][ty]){
    			// [12] 相邻位置可通行,步数+1,继续递归探索下一个位置
    			dfs(tx,ty,len+1); 
    		}
    	}
    }
    
    int main(){
    	// [13] 读取迷阵的行数n和列数m
    	cin>>n>>m;
    	// [14] 遍历迷阵,读取地图数据并完成初始化
    	for(int i=0;i<n;i++){
    		for(int j=0;j<m;j++){
    			cin>>arr[i][j];          // [15] 读取当前坐标的地图字符
    			dp[i][j]=INT_MAX;        // [16] 初始化所有位置步数为INT_MAX(暂未访问/不可达)
    			if(arr[i][j]=='@'){      // [17] 记录起点@的0-based坐标
    				a=i,b=j;
    			}
    			if(arr[i][j]=='*'){      // [18] 记录终点*的0-based坐标
    				c=i,d=j;
    			}
    		} 
    	}
    	// [19] 从起点开始DFS探索,初始累计步数为0
    	dfs(a,b,0);
    	// [20] 结果判断与输出:终点可达则输出累计步数,不可达则输出-1
    	if(dp[c][d]!=INT_MAX)
    		cout<<dp[c][d];
    	else
    		cout<<-1;
    	return 0; 
    }
    
    • 1

    信息

    ID
    1300
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    31
    已通过
    2
    上传者