红与黑（bfs&dfs)

红与黑（bfs&dfs)

文章目录

​​Question​​​​Ideas​​​​Code​​

Question

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。

请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入格式 输入包括多个数据集合。

每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。

在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下

1）‘.’：黑色的瓷砖； 2）‘#’：红色的瓷砖； 3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

输出格式 对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围 1≤W,H≤20 输入样例： 6 9 …#. …# … … … … … #@…# .#…#. 0 0 输出样例： 45

Ideas

bfs dfs

Code

# dfsN = 25dx = [1,-1,0,0]dy = [0,0,1,-1]def dfs(start): state[start[0]][start[1]] = 1 cnt = 1 # 起点也算 for i in range(4): x = start[0] + dx[i] y = start[1] + dy[i] if x < 0 or x >= h or y < 0 or y >= w: # 越界 continue if state[x][y]: # 走过 continue if locations[x][y] != '.': # 不能走 continue cnt += dfs((x,y)) return cntwhile 1: locations = [] state = [[0 for i in range(N)] for j in range(N)] # 记录是否走了 w,h = list(map(int,input().strip().split())) if w or h: for i in range(h): locations.append(input().strip()) else: break # 寻找起点 for i in range(h): for j in range(w): if locations[i][j] == '@': start = (i,j) print(dfs(start))

# bfsN = 25dx = [0,0,1,-1]dy = [1,-1,0,0]def bfs(start): cnt = 1 q = [start] stat[start[0]][start[1]] = 1 # 标记走过 while q: t = q.pop(0) #队首 for i in range(4): x = t[0] + dx[i] y = t[1] + dy[i] if 0<=x

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。