#! /usr/bin/env python3
# -*- coding: utf-8 -*-
# fileName ： robot_path.py
# author : zoujiameng@aliyun.com.cn

# 地上有一個(gè)m行和n列的方格。一個(gè)機(jī)器人從坐標(biāo)0,0的格子開(kāi)始移動(dòng)，每一次只能向左，右，上，下四個(gè)方向移動(dòng)一格，但是不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。 
# 例如，當(dāng)k為18時(shí)，機(jī)器人能夠進(jìn)入方格（35,37），因?yàn)?+5+3+7 = 18。但是，它不能進(jìn)入方格（35,38），因?yàn)?+5+3+8 = 19。請(qǐng)問(wèn)該機(jī)器人能夠達(dá)到多少個(gè)格子？
class Robot:
# 共用接口,判斷是否超過(guò)K
  def getDigitSum(self, num):
    sumD = 0
    while(num>0):
      sumD+=num%10
      num/=10
    return int(sumD)

  def PD_K(self, rows, cols, K):
    sumK = self.getDigitSum(rows) + self.getDigitSum(cols)
    if sumK > K:
      return False
    else:
      return True

  def PD_K1(self, i, j, k):
    "確定該位置是否可以走,將復(fù)雜約束條件設(shè)定"
    index = map(str,[i,j])
    sum_ij = 0
    for x in index:
      for y in x:
        sum_ij += int(y)
    if sum_ij <= k:
      return True
    else:
      return False

# 共用接口,打印遍歷的visited二維list
  def printMatrix(self, matrix, r, c):
    print("cur location(", r, ",", c, ")")
    for x in matrix:
      for y in x: 
        print(y, end=' ')
      print()

 #回溯法
  def hasPath(self, threshold, rows, cols):
    visited = [ [0 for j in range(cols)] for i in range(rows) ]
    count = 0
    startx = 0
    starty = 0
    #print(threshold, rows, cols, visited)
    visited = self.findPath(threshold, rows, cols, visited, startx, starty, -1, -1)
    for x in visited:
      for y in x:
        if( y == 1):
          count+=1
    print(visited)
    return count

  def findPath(self, threshold, rows, cols, visited, curx, cury, prex, prey):
    if 0 <= curx < rows and 0 <= cury < cols and self.PD_K1(curx, cury, threshold) and visited[curx][cury] != 1: # 判斷當(dāng)前點(diǎn)是否滿足條件
      visited[curx][cury] = 1
    self.printMatrix(visited, curx, cury)
    prex = curx
    prey = cury
    if cury+1 < cols and self.PD_K1(curx, cury+1, threshold) and visited[curx][cury+1] != 1: # east
      visited[curx][cury+1] = 1
      return self.findPath(threshold, rows, cols, visited, curx, cury+1, prex, prey)
    elif cury-1 >= 0 and self.PD_K1(curx, cury-1, threshold) and visited[curx][cury-1] != 1: # west
      visited[curx][cury-1] = 1
      return self.findPath(threshold, rows, cols, visited, curx, cury-1, prex, prey)
    elif curx+1 < rows and self.PD_K1(curx+1, cury, threshold) and visited[curx+1][cury] != 1: # sourth
      visited[curx+1][cury] = 1
      return self.findPath(threshold, rows, cols, visited, curx+1, cury, prex, prey)
    elif 0 <= curx-1 and self.PD_K1(curx-1, cury, threshold) and visited[curx-1][cury] != 1: # north
      visited[curx-1][cury] = 1
      return self.findPath(threshold, rows, cols, visited, curx-1, cury, prex, prey)
    else: # 返回上一層,此處有問(wèn)題
      return visited#self.findPath(threshold, rows, cols, visited, curx, cury, prex, prey)
 #回溯法2
  def movingCount(self, threshold, rows, cols):
    visited = [ [0 for j in range(cols)] for i in range(rows) ]
    print(visited)
    count = self.movingCountCore(threshold, rows, cols, 0, 0, visited);
    print(visited)
    return count

  def movingCountCore(self, threshold, rows, cols, row, col, visited):
    cc = 0
    if(self.check(threshold, rows, cols, row, col, visited)): 
      visited[row][col] = 1
      cc = 1 + self.movingCountCore(threshold, rows, cols, row+1, col,visited) + self.movingCountCore(threshold, rows, cols, row, col+1, visited) + self.movingCountCore(threshold, rows, cols, row-1, col, visited) + self.movingCountCore(threshold, rows, cols, row, col-1, visited)
    return cc

  def check(self, threshold, rows, cols, row, col, visited):
    if( 0 <= row < rows and 0 <= col < cols and (self.getDigitSum(row)+self.getDigitSum(col)) <= threshold and visited[row][col] != 1): 
      return True;
    return False 

# 暴力法，直接用當(dāng)前坐標(biāo)和K比較
  def force(self, rows, cols, k):
    count = 0
    for i in range(rows):
      for j in range(cols):
        if self.PD_K(i, j, k):
          count+=1
    return count
# 暴力法2, 用遞歸法來(lái)做
  def block(self, r, c, k): 
    s = sum(map(int, str(r)+str(c)))
    return s>k
  def con_visited(self, rows, cols):
    visited = [ [0 for j in range(cols)] for i in range(rows) ]
    return visited
  def traval(self, r, c, rows, cols, k, visited):
    if not (0<=r<rows and 0<=c<cols):
      return
    if visited[r][c] != 0 or self.block(r, c, k):
      visited[r][c] = -1
      return
    visited[r][c] = 1
    global acc
    acc+=1
    self.traval(r+1, c, rows, cols, k, visited)
    self.traval(r, c+1, rows, cols, k, visited)
    self.traval(r-1, c, rows, cols, k, visited)
    self.traval(r, c-1, rows, cols, k, visited)
    return acc

if __name__ == "__main__":
  # 調(diào)用測(cè)試
  m = 3
  n = 3
  k = 1
  o = Robot()
  print(o.hasPath(k, m, n))
  print(o.force(m,n,k))
  global acc
  acc = 0
  print(o.traval(0, 0, m, n, k, o.con_visited(m,n)))
  print(o.movingCount(k, m, n))