当前位置:   article > 正文

2024年华为OD机试题-欢乐的周末_华为od机考题2024

华为od机考题2024

题目描述

小华和小为是很要好的朋友,他们约定周末一起吃饭

通过手机交流,他们在地图上选择了多个聚餐地点(由于自然地形等原因,部分聚餐地点不可达)求小华和小为都能到达的聚餐地点有多少个?

输入描述

第一行输入m和n,m代表地图的长度,n代表地图的宽度第二行开始具体输入地图信息,地图信息包含:

0 为通畅的道路

1 为障碍物 (且仅1为障碍物)

2 为小华或者小为,地图中必定有且仅有2个(非障碍物)

3 为被选中的聚餐地点 (非障碍物)

输出描述

可以被两方都到达的聚餐地点数量,行未无空格

用例1

输入

4 4

2 1 0 3

0 1 2 1

0 3 0 0

0 0 0 0

输出

2

说明

第一行输入地图的长宽为4,4,接下来4行是地图2表示华为的位置,3是聚餐地点,图中的两个3,小华和小为都可到达,所以输出2

用例2

输入

4 4

2 1 2 3

0 1 0 0

0 1 0 0

0 1 0 0

输出

0

题解

  1. import sys
  2. def search_path(a, b, maps):
  3. to_visit = []
  4. m, n = len(maps[0]), len(maps)
  5. init = [(-1, 0), (1, 0), (0, 1), (0, -1)]
  6. for t in init:
  7. i, j = a[0] + t[0], a[1] + t[1]
  8. if i >= 0 and i < n:
  9. if j >= 0 and j < m:
  10. if maps[i][j] != 1:
  11. to_visit.append((i, j))
  12. if len(to_visit) == 0:
  13. return False
  14. for v in to_visit:
  15. m, n = v
  16. maps[m][n] = 1
  17. if m == b[0] and n == b[1]:
  18. # 找到目标点
  19. return True
  20. if not search_path(v, b, maps):
  21. continue
  22. else:
  23. return True
  24. return False
  25. maps = []
  26. p1 = []
  27. p2 = []
  28. p3 = []
  29. m, n = input().strip().split()
  30. m, n = int(m), int(n)
  31. for i in range(n):
  32. line = input().strip().split()
  33. if len(line) != m:
  34. continue
  35. temp = []
  36. for j in range(m):
  37. if line[j] == '1':
  38. p1.append((i, j))
  39. if line[j] == '2':
  40. p2.append((i, j))
  41. if line[j] == '3':
  42. p3.append((i, j))
  43. temp.append(int(line[j]))
  44. maps.append(temp)
  45. # print(maps)
  46. # print(p1)
  47. # print(p2)
  48. # print(p3)
  49. path = []
  50. for x in p2:
  51. for y in p3:
  52. # 构造一个记录是否点被访问过的二维数组
  53. visited = [[0] * m for i in range(n)]
  54. for p in p1:
  55. visited[p[0]][p[1]] = 1
  56. visited[x[0]][x[1]] = 1
  57. if search_path(x, y, visited):
  58. path.append((x, y))
  59. xiaohua = []
  60. xiaowei = []
  61. for v in path:
  62. if v[0] == p2[0]:
  63. xiaohua.append(v[1])
  64. if v[0] == p2[1]:
  65. xiaowei.append(v[1])
  66. cnt = 0
  67. for a in xiaohua:
  68. for b in xiaowei:
  69. if a == b:
  70. cnt = cnt + 1
  71. print(cnt)

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号