【剣指Offer】66.ロボットの運動範囲(Python実現)

1350 ワード

剣指オフ python データ構造アルゴリズムマシン学習

タイトルの説明
地上にはm行とn列の格子がある.1つのロボットは座標0,0の格子から移動し始め、毎回左、右、上、下の4つの方向に1格しか移動できませんが、行座標と列座標の数位の和がkより大きい格子に入ることはできません.例えば、kが18である場合、3+5+3+7=18であるため、ロボットは格子(35,37)に入ることができる.しかし,3＋5＋3＋8＝19のため,格子(35,38)に入ることはできなかった.すみません、このロボットは何個の格子に達することができますか?
解法一:再帰法

# -*- coding:utf-8 -*-
class Solution:
    def judge(self, threshold, i, j):
        # sum(map(int, str(i) + str(j)))       !             ! i,j   1          !
        if sum(map(int, str(i) + str(j))) <= threshold:
            return True 
        else:
            return False
    def findgrid(self, threshold, rows, cols, matrix, i, j):
        count = 0
        if i=0 and j>=0 and self.judge(threshold, i, j) and matrix[i][j] == 0: # matrix[i][j]==0        
            matrix[i][j] = 1  #        
            count = 1 + self.findgrid(threshold, rows, cols, matrix, i, j+1) \
            + self.findgrid(threshold, rows, cols, matrix, i, j-1) \
            + self.findgrid(threshold, rows, cols, matrix, i+1, j) \
            + self.findgrid(threshold, rows, cols, matrix, i-1, j)
        return count
    def movingCount(self, threshold, rows, cols):
        matrix = [[0 for i in range(cols)] for j in range(rows)]
        count = self.findgrid(threshold, rows, cols, matrix, 0, 0)
        print(matrix)
        return count

JBoss 6 Datasourceデータソース暗号解読メカニズム

Python学習エッセイ4:str,dic,setを用いる