https://www.acmicpc.net/problem/3085
initial
So we can swap 2 adjacent positions -up,left,down,right. But if we scan to our right, we dont have to swap to the left. ALSO additionally, if we scan in order from index [0][0] to [n-1][n-1], we only have to swap right and down (2 directions).
The general implementation is that for each grid, we check if swapping the adjacent right and down grid will make the whole board graph have a greater value for 1 consecutive row of same candies (same character). To check the longest possible row after swapping the right and down grid, lets create a separate check function.
This check function will scan from (1,n) and set default value as board[0][0]. If the grid has same value as this default value (previous left or up adjacent grid), then we increment count. Else if there is another character that is met, we reset count as 1.
VERY IMPT. I faced runtime error even though my ans was exactly the same. But passing parameter to your function like check(graph) actually improves time efficiency than just check(), which since parameter is not passed, global variable of graph is accessed instead of local variable. I thought it was just for modularity and clean code purposes.
Also i added if ans==n break but this doesnt seem to improve my time efficiency lol
solution
n = int(input())
graph = [list(input()) for _ in range(n)]
ans = 0
def check(graph):
tmp = 0
for i in range(n):
count = 1
for j in range(1, n):
if graph[i][j] == graph[i][j - 1]:
count += 1
else:
count = 1
tmp = max(tmp, count)
count = 1
for j in range(1, n):
if graph[j][i] == graph[j - 1][i]:
count += 1
else:
count = 1
tmp = max(tmp, count)
return tmp
for i in range(n):
for j in range(n):
if j + 1 < n:
graph[i][j], graph[i][j + 1] = graph[i][j + 1], graph[i][j]
ans = max(ans, check(graph))
if ans == n:
print(ans)
exit()
graph[i][j], graph[i][j + 1] = graph[i][j + 1], graph[i][j]
if i + 1 < n:
graph[i][j], graph[i + 1][j] = graph[i + 1][j], graph[i][j]
ans = max(ans, check(graph))
if ans == n:
print(ans)
exit()
graph[i][j], graph[i + 1][j] = graph[i + 1][j], graph[i][j]
print(ans)
complexity
Time Complexity:
The check function has a time complexity of O(n^2) because it iterates over each element of the matrix once.
The outer loop has a time complexity of O(n^2) as well since it iterates over each element of the matrix.
Overall, the time complexity is O(n^2) due to nested loops.
Space Complexity:
The space complexity is O(n^2) because you are storing the entire graph matrix.
Your code has a quadratic time and space complexity, which is acceptable given the constraints. If the input size increases significantly, you might want to explore more optimized algorithms.
