Это тонированная версия проблемы компьютерного зрения, которую мне нужно решить. Предположим, что вам заданы параметры n, q и приходится подсчитывать количество способов назначения целых чисел 0.. (q-1) элементам сетки n-на-n, так что для каждого присваивания все истинно
- Нет двух соседей (по горизонтали или по вертикали), получающих одинаковое значение.
- Значение в позициях (i, j) равно 0
- Значение в позиции (k, l) равно 0
Так как (i, j, k, l) не заданы, вывод должен быть массивом оценок выше, по одному для каждой допустимой установки (i, j, k, l)
Ниже приведен грубый подход. Цель состоит в том, чтобы получить эффективный алгоритм, который работает для q <= 100 и для n <= 18.
def tuples(n,q):
return [[a,]+b for a in range(q) for b in tuples(n-1,q)] if n>1 else [[a] for a in range(q)]
def isvalid(t,n):
grid=[t[n*i:n*(i+1)] for i in range(n)];
for r in range(n):
for c in range(n):
v=grid[r][c]
left=grid[r][c-1] if c>0 else -1
right=grid[r][c-1] if c<n-1 else -1
top=grid[r-1][c] if r > 0 else -1
bottom=grid[r+1][c] if r < n-1 else -1
if v==left or v==right or v==top or v==bottom:
return False
return True
def count(n,q):
result=[]
for pos1 in range(n**2):
for pos2 in range(n**2):
total=0
for t in tuples(n**2,q):
if t[pos1]==0 and t[pos2]==0 and isvalid(t,n):
total+=1
result.append(total)
return result
assert count(2,2)==[1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1]
Обновление 11/11 Я также спросил об этом на TopCoder forums, и их решение является наиболее эффективным из того, что я видел до сих пор (около 3 часов для n = 10, любой q, по оценке автора)
