地上有一个m行n列的方格, 一个机器人从坐标(0,0)的格子开始移动,
它每次可以向左,向右,向上,向下移动一格, 但不能进入行坐标和列坐标的位数
之和大于k的格子, 例如:当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18;
但它不能进入方格(35,38),因为3 + 5+3+8 = 19.请问该机器人最多能到达多少个格子?
回溯法,每次判断上下左右四个方向是否满足条件
python代码
# coding=utf-8 class solution(object): ''' 地上有一个m行n列的方格, 一个机器人从坐标(0,0)的格子开始移动, 它每次可以向左,向右,向上,向下移动一格, 但不能进入行坐标和列坐标的位数 之和大于k的格子, 例如:当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18; 但它不能进入方格(35,38),因为3 + 5+3+8 = 19.请问该机器人最多能到达多少个格子? ''' def solve(self, m, n, k): is_visited_array = [[false] * n] * m count = self.solve_count(0,0,is_visited_array, m, n, k) return count def solve_count(self, row, col, is_visited_array, m, n, k): count = 0 # print row,col if row >= 0 and col >= 0 and row < m and col < n and not is_visited_array[row][col] and self.is_sum(row, col, k) : # 雁过留声 is_visited_array[row][col] = true # 上下左右统计 count = 1 + self.solve_count(row - 1, col, is_visited_array, m, n, k) + self.solve_count(row, col - 1, is_visited_array, m, n, k) + \ self.solve_count(row + 1, col, is_visited_array, m, n, k) + self.solve_count(row, col + 1, is_visited_array, m, n, k) return count def is_sum(self, row, col, k): # 判断相加和是否符合规矩 row_sum = 0 col_sum = 0 while row > 10: row_sum += row / 10 row /= 10 row_sum += row while col > 10: col_sum += col / 10 col /= 10 col_sum += col return false if row_sum + col_sum > k else true if __name__ == '__main__': print solution().solve(35, 37,18)
如对本文有疑问, 点击进行留言回复!!
老猿学5G:融合计费场景的离线计费会话的Nchf_OfflineOnlyCharging_Release释放操作
老猿学5G扫盲贴:中国移动5G融合计费漫游计费架构和路由方案
老猿学5G扫盲贴:与用户和终端相关的名词UE、SUPI、GPSI、PEI
三星以核心技术优势持续更新折叠手机,华为缺乏自主技术无力应对
基于OpenCV+Python的均值滤波,高斯滤波,中值滤波,双边滤波
网友评论