1

我今天遇到了一个有趣的问题，我有点想找到一个解决方案。问题是：

机器人可以在网格周围移动。机器人从原点即(0, 0)出发，可以上下左右移动即(x, y+1)、(x, y-1)、(x-1, y)、(x) +1, y) 但有障碍物使机器人移动不安全。要检查一个点在网格上是否安全，取数字 x 的绝对和和数字 y 的绝对和并检查它是否小于或等于 23。即该点是否为 (39, 39) => 3 +9+3+9 是 24 并且该点不安全，或者如果 (-51, 7) => 5+1+7 是 13 那么它是安全的。问题陈述是找出机器人可以访问的区域有多大。

思考过程：

读完这个问题后的主要收获是找到位数小于或等于 23 的笛卡尔坐标，并根据坐标返回区域。现在有很多笛卡尔坐标可以限定为矩形或正方形，但它们都将具有相同的面积。现在我选择从原点制作一个正方形，使得 x==y 以及 x 和 y 的数字总和（即 x）<23，这可能看起来像

i = 0 
   while True:
       units, tens = i%10, (i/10)%10
       x =  units+tens
       y =  units+tens
       if x + y > 23:
           break;
       i+=1

但我认为我可能是错的，因为我返回 39 并且 x,y 坐标返回 (12, 12)。然后我必须计算（x，y），（-x，y），（-x，-y）和（x，-y）之间的面积。我认为我的方法是错误的，并且希望任何人对如何找到网格上最大的访问区域的想法

4

2 回答 2

2

编辑：如@David Choweller 所指出的，考虑负坐标。还通过删除一些不必要的索引使解决方案更干净。编辑：修复了总面积计算中的错误，感谢@polapts！

extent = 750
x_s = np.arange(-extent, extent+1, 1)
y_s = np.arange(-extent, extent+1, 1)

### Loop through each point and check if safe
coords = []
for y in y_s:
    x_coords = []
    for x in x_s:
        coords_digits_sum = sum([int(i) for i in str(abs(x))]) + sum([int(i) for i in str(abs(y))])
        if coords_digits_sum <= 23:
            safe = True
        else:
            safe = False
        x_coords.append(safe)
    coords.append(x_coords)


### Initialize the origin as `really_safe` point
coords[extent][extent] = 'really_safe' # Origin

### Iteratively check if a safe point is beside a `really_safe` point
changing = True
while changing == True:
    changing = False
    # Skip the first and last rows and columns because these are just paddings for looking up/down/left/right
    for y,x_coords in enumerate(coords[1:-1], start=1):
        for x,is_safe in enumerate(x_coords[1:-1], start=1):
            if is_safe == 'really_safe':
                continue
            ### look up, down, left, right of the point being checked
            elif is_safe and ('really_safe' in [coords[y-1][x], coords[y+1][x], coords[y][x-1], coords[y][x+1]]):
                coords[y][x] = 'really_safe'
                changing = True

### Count the number of "really safe" points only
really_safe_points = [[1 if safety == 'really_safe' else 0 for safety in x_coords[1:-1]] for x_coords in coords[1:-1]]
plt.imshow(really_safe_points)
plt.gca().invert_yaxis()

### Exclude first and last rows and columns in total area calculation since those were not iterated over 
plt.title(f"Accessible area: {sum([sum(i) for i in really_safe_points])}. Total area: {((extent-1)*2)**2}")
plt.show()

这是结果（可访问区域以黄色显示）： 在此处输入图像描述

在我看来，没有必要为无限板计算:)

于 2020-09-29T02:09:46.750 回答
0 
import matplotlib.pyplot as plt
def sum_of_digit(num):
    sum = 0
    while(num > 0):
        remainder = num % 10
        num = num // 10
        sum = sum + remainder
    return sum

memo = [[0] * 2000 for _ in range(2000)]
dp = [None] * 2000

area = 0
for i in range(-1000, 1000):
    for j in range(-1000, 1000):
        if dp[abs(i)] == None:
           dp[abs(i)] = sum_of_digit(abs(i))
        if dp[abs(j)] == None:
            dp[abs(j)] = sum_of_digit(abs(j))

        if dp[abs(i)] + dp[abs(j)] <= 23:
            memo[i+1000][j+1000] = 1
            area += 1
print(area)
plt.imshow(memo)
plt.gca().invert_yaxis()
plt.show()

结果

1253892

在此处输入图像描述

这个怎么样？但我认为这段代码不正确。因为结果太大了。

于 2020-11-17T01:10:29.290 回答