安徽天长建设局网站,设计公司海报,义乌外贸网站建设公司,学设计需要多少钱1818:红与黑
描述 有一间长方形的房子#xff0c;地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上#xff0c;只能向相邻的黑色瓷砖移动。请写一个程序#xff0c;计算你总共能够到达多少块黑色的瓷砖。 输入 包括多个数据集合。每个数据集合的第一行…1818:红与黑
描述 有一间长方形的房子地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上只能向相邻的黑色瓷砖移动。请写一个程序计算你总共能够到达多少块黑色的瓷砖。 输入 包括多个数据集合。每个数据集合的第一行是两个整数W和H分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中每行包括W个字符。每个字符表示一块瓷砖的颜色规则如下 1‘.’黑色的瓷砖 2‘#’红色的瓷砖 3‘’黑色的瓷砖并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时表示输入结束。 输出 对每个数据集合分别输出一行显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。 样例输入
6 9
....#.
.....#
......
......
......
......
......
#...#
.#..#.
0 0样例输出
45【题目解析】
本题需要求“”所在的连通块大小。从起点开始利用洪水填充法将同一个连通块的瓷砖全部标记。根据模板框架先界定清楚几个细节 1.状态描述当前局面情况的数学表示一般是位置信息、时间信息等。在本题中利用两个整数x,y表示当前所在的位置表示当前在第x行、第y列。我们通常使用行列坐标而不是坐标轴的坐标以便于跟二维数组的下标对应起来。根据题意起始状态便是“”所在的位置。 2.标记利用二维数组 v i s [ x ] [ y ] t r u e vis[x][y]true vis[x][y]true,表示当前点x,y已经被染色。vis初始为 f a l s e false false,表示所有的点没有被染色。
代码如下
#includebits/stdc.h
using namespace std;
char a[21][21];
int w,h,cnt;
bool vis[21][21];
int dx[]{0,0,1,-1};
int dy[]{1,-1,0,0};void dfs(int x,int y){vis[x][y]1;//当前点标记cnt;for(int i0;i4;i){int nxxdx[i];int nyydy[i];if(nx1||ny1||nxh||nyw)continue;//出地图if(a[nx][ny]!.)continue;//如果不是黑砖if(vis[nx][ny])continue;//已经在当前路径中dfs(nx,ny);}
}int main(){while(true){cinwh;if(!w!h)break;int sx-1,sy-1;for(int i1;ih;i){cin(a[i]1);for(int j1;jw;j){if(a[i][j]){sxi;syj;}}}if(sx-1 sy-1){cout0endl;continue;}cnt0;//多组数据需要把数组初始化memset(vis,false,sizeof(vis));dfs(sx,sy);coutcntendl;}return 0;
}在深度优先搜索的使用上还可以使用另外一种方式
void dfs(int x,int y){for(int i0;i4;i){int nxxdx[i];int nyydy[i];if(nx1||ny1||nxh||nyw)continue;//出地图if(a[nx][ny]!.)continue;if(vis[nx][ny])continue;//已经在当前路径中vis[nx][ny]1;//标记cnt;dfs(nx,ny); }
}这种方式不会处理当前点的状态使用原方式的main函数会缺少起始点的黑砖所以需要对main函数进行修改。完整代码如下
#includebits/stdc.h
using namespace std;
char a[21][21];
int w,h,cnt;
bool vis[21][21];
int dx[]{0,0,1,-1};
int dy[]{1,-1,0,0};void dfs(int x,int y){for(int i0;i4;i){int nxxdx[i];int nyydy[i];if(nx1||ny1||nxh||nyw)continue;//出地图if(a[nx][ny]!.)continue;if(vis[nx][ny])continue;//已经在当前路径中vis[nx][ny]1;//标记cnt;dfs(nx,ny); }
}int main(){while(true){cinwh;if(!w!h)break;int sx-1,sy-1;for(int i1;ih;i){cin(a[i]1);for(int j1;jw;j){if(a[i][j]){sxi;syj;cnt1;//记录起始点的黑砖}}}if(sx-1 sy-1){cout0endl;continue;}memset(vis,false,sizeof(vis));dfs(sx,sy);coutcntendl;}return 0;
}
