4
私はここで言及したくない特定のWebサイトからプログラミング課題の問題を解決しようとしています。Pythonコードを最適化し、割り当て/割り当て解除時間を短縮する
次のように問題がある：
N * Nポイントの正方形ボードがあります。昆虫は特定の点（x1、y1）から始まります。 | x1-x2 | + | y1-y2 |ならば、任意の点（x2、y2）にジャンプすることができます。 < = S。また、いくつかの点には昆虫がジャンプできない水が含まれています。 Mジャンプでは、いくつのパスを取ることができますか？ジャンプすることで同じ位置に留まることに注意してください。
整数N、S、Mが与えられたので、最初のボードの設定があります。
私の解決策は正しいと確信しており、誘導によって証明することができます。私はボードを有効な昆虫ジャンプをするポイント間のエッジを持つグラフ（隣接リスト）に変換します。その後、M回の反復とパスカウントの更新の問題です。
私の主な関心事は、複数のテストケースで動作するようにコードを最適化する必要があることです。これは、実行時間を遅くする割当て/割り当て解除を何度も行わないことです。アルゴリズムそのものの中で誰かが最適化を提案できるならば、それは素晴らしいことかもしれません。
ありがとうございます！
import sys
#The board on which Jumping insect moves.
#The max size in any test case is 200 * 200
board = [['_']*200 for j in xrange(200)]
#Graph in the form of an adjancency list created from the board
G = [list() for i in xrange(200*200)]
def paths(N,M,S):
'''Calculates the total number of paths insect takes
The board size is N*N, Length of paths: M,
Insect can jusp from square u to square v if ||u-v|| <=S
Here ||u-v|| refers to the 1 norm'''
# Totals paths are modulo 1000000007
MOD = 1000000007
# Clearing adjacency list for this testcase
for i in xrange(N*N): del(G[i][:])
s = -1 #Starting point s
#Creating G adjacency list
# Point 'L' represents starting point
# Point 'P' cannot be accessed by the insect
for u in xrange(N*N):
x1, y1 = u/N, u%N
if board[x1][y1] == 'L': s = u
elif board[x1][y1] == 'P': continue
for j in xrange(S+1):
for k in xrange(S+1-j):
x2, y2 = x1+j, y1+k
if x2 < N and y2 < N and not board[x2][y2] == 'P':
v = x2*N+y2
G[u].append(v)
if not u == v: G[v].append(u)
if j > 0 and k > 0:
x2, y2 = x1+j, y1-k
if x2 < N and y2 >= 0 and not board[x2][y2] == 'P':
v = x2*N+y2
G[u].append(v)
G[v].append(u)
# P stores path counts
P = [[0 for i in xrange(N*N)] for j in xrange(2)]
# Setting count for starting position to 1
P[0][s] = 1
# Using shifter to toggle between prev and curr paths
shifter, prev, curr = 0, 0, 0
# Calculating paths
for i in xrange(M):
prev, curr = shifter %2, (shifter+1)%2
#Clearing Path counts on curr
for i in xrange(N*N): P[curr][i] = 0
for u in xrange(N*N):
if P[prev][u] == 0: continue
for v in G[u]:
P[curr][v] = (P[curr][v]+P[prev][u]) % MOD
shifter = (shifter+1)%2
return (sum(P[curr])%MOD)
#Number of testcases
num = int(sys.stdin.readline().split()[0])
results = []
# Reading in test cases
for i in xrange(num):
N, M, S = [int(j) for j in sys.stdin.readline().split()]
for j in xrange(N):
board[j][:N] = list(sys.stdin.readline().split()[0])
results.append(paths(N,M,S))
for result in results:
print result