本文實例為大家分享了python實現機器人行走效果的具體代碼，供大家參考，具體內容如下
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
#! /usr/bin/env python3# -*- coding: utf-8 -*-# fileName ： robot_path.py# author : [email protected]# 地上有一個m行和n列的方格。一個機器人從坐標0,0的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行坐標和列坐標的數位之和大于k的格子。 # 例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18。但是，它不能進入方格（35,38），因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子？class Robot:# 共用接口,判斷是否超過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): "確定該位置是否可以走,將復雜約束條件設定" 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: # 判斷當前點是否滿足條件 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: # 返回上一層,此處有問題 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# 暴力法，直接用當前坐標和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, 用遞歸法來做 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 accif __name__ == "__main__": # 調用測試 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)) |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://blog.csdn.net/shentong1/article/details/78775710
