1 条题解

  • 0
    @ 2026-2-4 19:02:57
    #include <bits/stdc++.h>
    using namespace std;
    
    // [1] 定义坐标结构体,a表示行坐标,b表示列坐标
    struct stu{
    	int a,b;
    };
    // [2] 路径存储数组,按访问顺序保存从起点到当前点的所有坐标
    vector<stu> arr;
    
    // [3] 迷宫的行数和列数
    int n,m;
    // [4] 迷宫地图存储数组,crr[i][j]表示第i行第j列的格子状态('o'可走/'#'不可走)
    char crr[110][110];
    // [5] 访问标记数组,flag[i][j]=1表示坐标(i,j)已访问,避免重复走
    int flag[110][110]={};
    
    // [6] 方向偏移量数组,严格遵循题目策略顺序:右→下→左→上
    int dx[4]={0,1,0,-1};
    // [7] 对应dx的列方向偏移量,与dx一一对应
    int dy[4]={1,0,-1,0};
    // [8] 有效路径计数变量,记录找到的路径序号,初始为0
    int sum=0;
    
    // [16] 深度优先搜索(DFS)核心函数,参数x为当前行坐标,y为当前列坐标
    void dfs(int x,int y){
    	// [17] 递归终止条件:到达终点(n,m),输出当前有效路径
    	if(x==n && y==m){
    		sum++; // [18] 有效路径计数自增
    		cout<<sum<<":"<<arr[0].a<<","<<arr[0].b; // [19] 输出路径序号和起点坐标
    		// [20] 循环输出路径中后续的所有坐标节点
    		for(int i=1;i<arr.size();i++){
    			cout<<"->"<<arr[i].a<<","<<arr[i].b; // [21] 拼接输出路径节点,格式为「->行,列」
    		}
    		cout<<endl; // [22] 换行分隔不同路径,保证输出整洁
    		return ; // [23] 递归返回,结束当前路径的后续搜索
    	}
    	
    	// [24] 按「右→下→左→上」的顺序尝试四个方向移动
    	for(int i=0;i<4;i++){
    		int tx=x+dx[i]; // [25] 计算下一个候选点的行坐标
    		int ty=y+dy[i]; // [26] 计算下一个候选点的列坐标
    		// [27] 候选点合法性判断:在迷宫范围内、未被访问、是可走的格子('o')
    		if((tx>=1 && tx<=n) && (ty>=1 && ty<=m) && flag[tx][ty]==0 && crr[tx][ty]=='o'){
    			flag[tx][ty]=1; // [28] 标记候选点为已访问,防止重复遍历
    			arr.push_back({tx,ty}); // [29] 将候选点加入路径数组,记录当前路径
    			dfs(tx,ty); // [30] 递归调用DFS,搜索候选点出发的后续路径
    			arr.pop_back(); // [31] 路径回溯:弹出当前点,恢复上一步的路径状态
    			flag[tx][ty]=0; // [32] 标记回溯:取消候选点的已访问状态,恢复可遍历
    		}
    	}
    }
    
    // [9] 主函数,程序执行入口
    int main(){
    	cin>>n>>m; // [10] 输入迷宫的行数n和列数m
    	// [11] 读入n行迷宫地图,每行m个字符
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			cin>>crr[i][j]; // [12] 读入第i行第j列的格子状态
    		} 
    	}
    	
    	flag[1][1]=1; // [13] 标记起点(1,1)为已访问,避免重复访问
    	arr.push_back({1,1}); // [14] 将起点坐标加入路径数组,初始化路径
    	dfs(1,1); // [15] 从起点(1,1)开始深度优先搜索,跳转至[16]开始注释DFS逻辑
    	
    	// [33] 题目要求:无有效路径时输出"no",原有代码缺失此逻辑,此处补充
    	if(sum == 0) {
    		cout << "no" << endl;
    	}
    	
    	return 0; // [34] 程序正常执行完毕,返回终止状态码0
    }
    

    信息

    ID
    1292
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者