华为机试二星题--机器人走迷宫
机器人走一个迷宫,给出迷宫的x和y(x*y的迷宫)并且迷宫中有障碍物,输入k表示障碍物有k个,并且会将障碍物的坐标挨个输入.
机器人从0,0的位置走到x,y的位置并且只能向x,y增加的方向走,不能回退.
如代码类注释展示的样子,#表示可以走的方格,0代表障碍,机器人从0,0的位置只能向下或者向前走到出口.
其中会有不可达方格和陷阱方格.不可达方格为第四行前三个,该机器人在行走路径上不可能走到的方格,陷阱方格如第一行最后两个,走进之后则不能抵达终点.
#华为##华为笔试#
机器人从0,0的位置走到x,y的位置并且只能向x,y增加的方向走,不能回退.
如代码类注释展示的样子,#表示可以走的方格,0代表障碍,机器人从0,0的位置只能向下或者向前走到出口.
其中会有不可达方格和陷阱方格.不可达方格为第四行前三个,该机器人在行走路径上不可能走到的方格,陷阱方格如第一行最后两个,走进之后则不能抵达终点.
要求: 输出陷阱和不可达方格方格数量
来一个python版 我个人认为这就是回溯吧 这些叫法有点分不清o.o
x,y=map(int,input().split()) k=int(input()) a=[] for i in range(k): a.append(list(map(int,input().split()))) b = [[0]*y for j in range(x)] for i in a: b[i[0]][i[1]]=-1 def run(i,j,b): b[i][j]=1 if i==x-1 and j==y-1: return b if i+1<x and b[i+1][j]==0: b=run(i+1,j,b) if j+1<y and b[i][j+1]==0: b=run(i,j+1,b) if (i+1>=x or b[i+1][j]==-1 or b[i+1][j]==2) and (j+1>=y or b[i][j+1]==-1 or b[i][j+1]==2): b[i][j]=2 if i-1>=0 and b[i-1][j]==1: b=run(i-1,j,b) if j-1>=0 and b[i][j-1]==1: b=run(i,j-1,b) return b b=run(0,0,b) k=0 #陷阱标为0 c=0 #不可达标为2 for i in range(len(b)): for j in range(len(b[0])): if b[i][j]==0: c+=1 elif b[i][j]==2: k+=1 print(k,c)
