找到机器人可以安全访问网格上的点的最大区域

Question

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

机器人可以在网格中移动。机器人从原点(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)之间的面积。我认为我的方法是错误的，希望大家对如何在网格上找到最大的访问区域有一些想法。

Answer 1

编辑:正如@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()

这是结果(可访问的区域以黄色显示)：

​

在我看来，对于无限大的板，似乎没有必要进行计算:)

Answer 2

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

​

​

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