1 条题解

  • 0
    @ 2026-1-27 23:04:32
    #include <bits/stdc++.h>
    using namespace std;
    
    // [1] arr数组-存储瓷砖状态:0=黑色瓷砖(.或起点@)、1=红色瓷砖(#,不可通行)、2=已访问的黑色瓷砖(避免重复计数)
    int arr[200][200];
    // [2] 四个方向偏移量(右、下、左、上),用于遍历当前瓷砖的上下左右相邻位置
    int dx[4]={0,1,0,-1};
    int dy[4]={1,0,-1,0};
    // [3] n-瓷砖矩阵的行数(对应输入的H);m-瓷砖矩阵的列数(对应输入的W);sum-统计可达的黑色瓷砖总数(包含起点)
    int n,m,sum=0;
    
    // [4] DFS递归函数:从当前瓷砖出发,遍历所有连通的黑色瓷砖,标记为已访问并累计数量
    // 参数说明:x-当前瓷砖的横坐标(行号);y-当前瓷砖的纵坐标(列号)
    void dfs(int x,int y){
        // [5] 递归终止条件:当前瓷砖是红色(1)或已访问(2),直接返回
    	if(arr[x][y]==1 || arr[x][y]==2) return;
        // [6] 若当前是未访问的黑色瓷砖(0),计数+1
    	if(arr[x][y]==0) sum++;
        // [7] 标记当前瓷砖为已访问(2),避免后续重复遍历
    	arr[x][y]=2;
        // [8] 遍历四个方向,扩展当前瓷砖的连通区域
    	for(int i=0;i<4;i++){
            // [9] 计算相邻瓷砖的横坐标和纵坐标
    		int tx=x+dx[i];
    		int ty=y+dy[i];
            // [10] 合法性判断:相邻瓷砖在矩阵范围内,且是未访问的黑色瓷砖(0)
    		if(tx>=0 && tx<n && ty>=0 && ty<m && arr[tx][ty]==0){
                // [11] 递归遍历相邻的黑色瓷砖
    			dfs(tx,ty);
    		}	
    	}
    }
    
    int main(){
        // [12] 读取瓷砖矩阵的列数m(W)和行数n(H)
    	cin>>m>>n;
    	char c;
        // [13] vx,vy-起点@的横坐标(行号)和纵坐标(列号)
    	int vx=0,vy=0;
        // [14] 遍历矩阵,读取每个瓷砖的颜色并转换为状态值
    	for(int i=0;i<n;i++){
    		for(int j=0;j<m;j++){
    			cin>>c;
    			if(c=='.'){
                    // [15] 普通黑色瓷砖,状态设为0
    				arr[i][j]=0;
    			}else if(c=='#'){
                    // [16] 红色瓷砖,状态设为1(不可通行)
    				arr[i][j]=1;
    			}else{
                    // [17] 起点@,状态设为0(黑色瓷砖),并记录起点坐标
    				arr[i][j]=0;
    				vx=i;
    				vy=j;
    			}
    		}
    	}
        // [18] 从起点开始DFS,统计可达的黑色瓷砖数量
    	dfs(vx,vy);
        // [19] 输出可达的黑色瓷砖总数
    	cout<<sum;
    	return 0;
    }
    
    • 1

    信息

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