1 条题解
-
0
#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
- 上传者