I am trying to solve a problem as described below:
You are given an input of a n*m forest.
You have to answer a group of inquiries. Your task is to return the number of trees for every inquiry.
Input: In the first line you are given 3 integers; n,m and q. This means that the size of the forest is n×m squares and the number of inquiries is q.
Then you get n rows that describe the forest. Every square is either blank (.) or a tree (*).
Then you are given q lines of inquiries. Every line has 4 integers y1, x1, y2 and x2, that define the area.
Output: Return the number of trees in the inquired area.
4 7 3 .*...*. **..*.* .**.*.. ......* 1 1 2 2 3 2 4 7 2 5 2 5
3 4 1
My code is below; first it initializes the array so that every square is initialized to the number of trees in the rectangle from the top left square to the square. That takes O(n^2). After that I am able to answer the inquiries in O(1).
firstline = input().split() rownumber = int(firstline) #How many rows rowlength = int(firstline) #How many columns numberOfInquiries = int(firstline) forest =  def printOut(someList): for x in range(0, len(someList)): print(someList[x]) #This function exist just for debugging for x in range(0, rownumber): forest.append() UI = list(input()) if UI == ".": first = 0 else: first = 1 forest[x].append(first) for y in range(1, rowlength): if UI[y] == "*": forest[x].append(int(forest[x][y-1])+1) else: forest[x].append(int(forest[x][y-1])) for column in range(0, rowlength): for row in range(1, rownumber): forest[row][column] += forest[row-1][column] print("") #Everything is initialized for x in range(0, numberOfInquiries): UI = input().split() y1 = int(UI)-1 x1 = int(UI)-1 y2 = int(UI)-1 x2 = int(UI)-1 first = forest[y2][x2] second = forest[y1-1][x2] third = forest[y2][x1-1] fourth = forest[y1-1][x1-1] if x1 == 0: third = 0 fourth = 0 if y1 == 0: second = 0 fourth = 0 print(first-second-third+fourth)
My question remains: how can this be optimized? The initialization takes 0.7-0.8 s in the larger cases and answering the inquiries also takes about the same. This is about 50% too slow for the largest test cases (time limit =1s). Are those just too much for Python? Most of the people solving these problems use C++.