蒜厂有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。
请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
输入格式
第一行是两个整数 WW 和 HH,分别表示 xx 方向和 yy 方向瓷砖的数量。WW 和 HH 都不超过 2020。
在接下来的 HH 行中,每行包括 WW 个字符。每个字符表示一块瓷砖的颜色,规则如下
1)’.’:黑色的瓷砖;
2)’#’:红色的瓷砖;
3)’@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
输出格式
输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
输入样例
6 9
…#.
…#
…
…
…
…
…
#@…#
.#…#.
输出样例
45
这道题是一道经典的图的搜索,用dfs,深度优先搜索算法来解决,具体的思路是,以@的位置为起点,分别对@的上下左右四个位置进行搜索,如果这个位置合法(位置没有超出界限,位置是黑色的瓷砖)且该位置之前没有被走过,那么我们就对该位置进行标记(本题我记为8),并且以该位置为新的起点,开始新的搜索,即递归调用函数。
实现方面,用变量count记录我们走过的黑色瓷砖,我们可以开一个和输入一样大的状态矩阵st,st为0表示该位置是黑色的瓷砖(合法),st为1则表示为红色的瓷砖,即该位置不可用,每当走过一个之前未被走过的黑色瓷砖,我们就将其置为8,并且count加一,最后输出count。
#includeusing namespace std; const int N = 25; char map[N][N]; int st[N][N]; int W, H; int x, y; int dx[4] = {0, -1, 0, 1}; // 右, 下, 左, 上 int dy[4] = {1, 0, -1, 0}; int count = 1; void dfs(int x, int y); int main() { cin >> W >> H; // W列,H行 for (int i = 1; i <= H; i ++ ) for (int j = 1; j <= W; j ++ ) { cin >> map[i][j]; if (map[i][j] == '.') st[i][j] = 0; else if (map[i][j] == '#') st[i][j] = 1; else if (map[i][j] == '@') { x = i; // 初始行数 y = j; // 初始列数 } } dfs(x, y); cout << count; return 0; } void dfs(int x, int y) { st[x][y] = 8; for (int i = 0; i <= 3; i ++ ) { if (st[x + dx[i]][y + dy[i]] == 0 && x+dx[i] >= 1 && x+dx[i] <= H && y+dy[i] >= 1 && y+dy[i] <= W) { count++; dfs(x + dx[i], y + dy[i]); } } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)