代码收藏家技术教程 2022-07-28

华为OD机试真题：欢乐的周末

■ 题目描述

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

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

输入描述

第一行输入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

说明

第一行输入地图的长宽为3和4。

第二行开始为具体的地图，其中：3代表小华和小明选择的聚餐地点；2代表小华或者小明（确保有2个）；0代表可以通行的位置；1代表不可以通行的位置。

此时两者能都能到达的聚餐位置有2处。

示例2 输入输出示例仅供调试，后台判题数据一般不包含示例

输入

4 4

2 1 2 3

0 1 0 0

输出

0

说明

第一行输入地图的长宽为4和4。

由于图中小华和小为之间有个阻隔，此时，没有两人都能到达的聚餐地址，故而返回0。

备注:

地图的长宽为m和n，其中：

4 <= m <= 100

4 <= n <= 100

聚餐的地点数量为 k，则

1< k <= 100

#解题想法：把每个人可能到达的地点全部用dfs求出，再通过原来的l中目的地为3和这两个人是否
都能到达来获取结果


测试用例：
4 4
2 1 0 3
0 1 2 1
0 3 2 0
0 1 0 0


while 1:
    try:
        import copy



        m, n = input().split(" ")

        m = int(m)
        n = int(n)

        l = []
        for _ in range(m):
            s = list(map(int, input().split()))
            l.append(s)


        #深度赋值l，因为dfs函数会改变传入参数ll的值，所以用一个复制一个
        l1= copy.deepcopy(l)   
        l2 =copy.deepcopy(l)

        tmp=[]
        for i in range(m):
            for j in range(n):
                if l[i][j]==2:
                    tmp.append([i,j])


        res1 = [[0] * m for _ in range(n)]
        res2 = [[0] * m for _ in range(n)]

        px=[-1,0,1,0]
        py=[0,-1,0,1]


        def dfs(ll,res,i,j,flag):

            for index in range(0,len(px)):
                new_x=i+px[index]
                new_y = j + py[index]

                if new_x<m and new_x>=0 and new_y<n and new_y>=0 and ll[new_x][new_y]!=1 and not flag:
                    ll[new_x][new_y]=1
                    res[new_x][new_y]=1

                    dfs(ll,res,new_x,new_y,flag)

                    ll[new_x][new_y]=0


        flag = False
        dfs(l1,res1,tmp[0][0],tmp[0][1],flag)


        flag = False
        dfs(l2, res2, tmp[1][0], tmp[1][1], flag)

        print("初始条件")
        for line1 in l:
            print(line1)

        print("第一个人可到达的路线")
        for line2 in res1:
            print(line2)


        print("第二个人可到达的路线")
        for line3 in res2:
            print(line3)


        result=0
        for i in range(m):
            for j in range(n):
                if l[i][j] == 3 and res1[i][j]==1 and res2[i][j]==1:
                    result+=1

        print()
        print("result:",result)


    except:
        break