[백준] 1080번: 행렬

https://www.acmicpc.net/problem/1080

initial

very good animation:
https://puleugo.tistory.com/39

My initial approach was to compare just 1 row or 1 column one at a time. If it is the same as the final matrix’s row, we dont reverse it else we reverse.

But this is problematic if matrix is like 4x4. Do we compare row or col first? Do we go right or down first? I was gonna make it like bfs but no the logic is just iterating up to n-2 and m-2 where we go right all the way first and increment row and go right all the way and so on like a scan. If we meet a value that is not equal, we reverse the matrix and increment count. The final check has to be done on the 2 matrixes if they are really equal after all the reversing and if not, we return -1 else we return count.

When matrix is smaller than 3x3 matrix, we can just compare with the object equality. BTW very important. == in Java is object identity, which compares the references if they point to the same memory address. But in python, == is object equality, which compares the values. Object identity in python is using the keyword is.

3 mistakes
1) When input is given with no space like 0010 and we want to make that become [0,0,1,0], the usual list(map(int,input().split()) does not work because split only works on some space in between (whitespace) the numbers but in this input, there is no space in between. So we have to just take the whole thing and convert it to a list first and then map each element to an int. We store the mapped result into a list as the final step. Like list(map(int,list(input())))

2) When reversing the list, I thought we could just do mat[i][j]!=mat[i][j] cuz the value is either 0 or 1 so adding boolean not operator will turn it to 1 and 0 respectively. But this is wrong.

3) I always added input=sys.stdin.readline but for this code case, I get value error. This readline takes the whole input as 1 whole string including the newline character ('\n') at the end. Apparently input.rstrip() works but not sure tbc

solution

import sys

n, m = map(int, input().split())
ori = [list(map(int, list(input()))) for _ in range(n)]
final = [list(map(int, list(input()))) for _ in range(n)]

def reverse(mat, i, j):
    for a in range(i, i+3):
        for b in range(j, j+3):
            if mat[a][b]==0:
                mat[a][b]=1
            else:
                mat[a][b]=0
           

count = 0

if n < 3 or m < 3:
    if ori != final:
        print(-1)
    else:
        print(0)
    exit()

for i in range(n-2):
    for j in range(m-2):
        if ori[i][j] != final[i][j]:
            reverse(ori, i, j)
            count += 1

if ori != final:
    print(-1)
else:
    print(count)

complexity

The time and space complexity of this code depends on the size of the input matrix, which is n x m.

Time Complexity:

• The code uses two nested loops to iterate over the elements of the matrix (ori and final). The outer loop runs n-2 times, and the inner loop runs m-2 times.
• The reverse function is called within the nested loops, but its time complexity is constant because it always performs a fixed number of operations.

Therefore, the overall time complexity is O(n * m), where n and m are the dimensions of the input matrix.

Space Complexity:

• The space complexity is determined by the size of the input matrices ori and final. Each matrix has n rows and m columns.
• Additional space is used for variables like count, i, j, a, b, and the reverse function parameters.

Therefore, the overall space complexity is O(n * m).

Keep in mind that this analysis assumes that operations like list indexing and arithmetic operations on integers take constant time, which is generally true in practice for moderate-sized matrices.