I am trying to solve a programming task from a specific site, which I would not want to mention here.
The problem is this:
There is a square board with N * N dots. The population begins at a certain point (x1, y1). It can go to any point (x2, y2) if | x1-x2 | + | y1-y2 | <= S. In addition, some points contain water on which the insect cannot jump. How many different paths can you take in M jumps? Note that he can stay at one point, jumping into place.
Given integers N , S , M , as well as the initial configuration of the board.
I am sure that my decision is correct and can be proved by induction. I convert a board to a graph (adjacency list) with edges between the points that make a real insect jump. Then it is just a matter of repeating M times and updating the path.
My main problem is that the code needs to be optimized so that it works on several test cases without allocating / de-classifying too many times, which slows down the time. It would also be great if someone could offer optimization within the algorithm itself.
Thanks!
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 ||uv|| <=S Here ||uv|| 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