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

Question

我今天遇到了一个有趣的问题，我有点被一个解决方案绊倒了。问题是:

机器人可以在网格上移动。机器人从原点即（0，0）开始，可以上下左右移动，即（x，y+1），（x，y-1），（x-1，y）和（x+1，y），但移动机器人时会遇到障碍物。要检查网格上的点是否安全，请取数字x和数字y的绝对和，然后检查其是否小于或等于23。i、 e如果该点为（39,39）=>；3+9+3+9为24且该点不安全，或者如果（-51,7）=>；5+1+7等于13，那么就安全了。问题是找出机器人能进入的区域有多大

思维过程：

阅读此问题后的主要收获是找到数字小于或等于23的笛卡尔坐标，并基于坐标返回区域。现在有很多笛卡尔坐标，它们可以限定并形成矩形或正方形，但是它们都有相同的面积。现在我选择从原点生成一个正方形，这样x==y和x和y的数字之和（即x）<；这看起来像

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

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

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

Answer 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()

这是结果（黄色显示的可访问区域）：

在我看来，对于一个无限大的电路板，似乎不需要计算：）