赞
踩
小华和小为是很要好的朋友,他们约定周末一起吃饭
通过手机交流,他们在地图上选择了多个聚餐地点(由于自然地形等原因,部分聚餐地点不可达)求小华和小为都能到达的聚餐地点有多少个?
第一行输入m和n,m代表地图的长度,n代表地图的宽度第二行开始具体输入地图信息,地图信息包含:
0 为通畅的道路
1 为障碍物 (且仅1为障碍物)
2 为小华或者小为,地图中必定有且仅有2个(非障碍物)
3 为被选中的聚餐地点 (非障碍物)
可以被两方都到达的聚餐地点数量,行未无空格
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
4 4
2 1 2 3
0 1 0 0
0 1 0 0
0 1 0 0
0
- import sys
-
-
- def search_path(a, b, maps):
- to_visit = []
- m, n = len(maps[0]), len(maps)
- init = [(-1, 0), (1, 0), (0, 1), (0, -1)]
- for t in init:
- i, j = a[0] + t[0], a[1] + t[1]
- if i >= 0 and i < n:
- if j >= 0 and j < m:
- if maps[i][j] != 1:
- to_visit.append((i, j))
- if len(to_visit) == 0:
- return False
- for v in to_visit:
- m, n = v
- maps[m][n] = 1
- if m == b[0] and n == b[1]:
- # 找到目标点
- return True
- if not search_path(v, b, maps):
- continue
- else:
- return True
- return False
-
-
- maps = []
- p1 = []
- p2 = []
- p3 = []
- m, n = input().strip().split()
- m, n = int(m), int(n)
- for i in range(n):
- line = input().strip().split()
- if len(line) != m:
- continue
- temp = []
- for j in range(m):
- if line[j] == '1':
- p1.append((i, j))
- if line[j] == '2':
- p2.append((i, j))
- if line[j] == '3':
- p3.append((i, j))
- temp.append(int(line[j]))
- maps.append(temp)
- # print(maps)
- # print(p1)
- # print(p2)
- # print(p3)
- path = []
- for x in p2:
- for y in p3:
- # 构造一个记录是否点被访问过的二维数组
- visited = [[0] * m for i in range(n)]
- for p in p1:
- visited[p[0]][p[1]] = 1
- visited[x[0]][x[1]] = 1
-
- if search_path(x, y, visited):
- path.append((x, y))
-
- xiaohua = []
- xiaowei = []
- for v in path:
- if v[0] == p2[0]:
- xiaohua.append(v[1])
- if v[0] == p2[1]:
- xiaowei.append(v[1])
- cnt = 0
- for a in xiaohua:
- for b in xiaowei:
- if a == b:
- cnt = cnt + 1
- print(cnt)

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。