Missing Test Case - 782. Transform to Chessboard #19344
Description
LeetCode Username
metaphysicalist
Problem number, title, and link
- Transform to Chessboard] https://leetcode.com/problems/transform-to-chessboard/
Category of the bug
- Missing test Case (Incorrect/Inefficient Code getting accepted because of missing test cases)
Description of the bug
My following code gets Accepted. However, the code outputs a wrong answer for my test case:
[[0, 0, 1], [1, 1, 0], [1, 0, 1]]
My code outputs 1, however, the correct answer is -1.
Language used for code
Python 3
Code used for Submit/Run operation
class Solution:
def movesToChessboard(self, board: List[List[int]]) -> int:
n = len(board)
board1 = [[(i + j) % 2 for j in range(n)] for i in range(n)]
board2 = [[1 - ((i + j) % 2) for j in range(n)] for i in range(n)]
def encode(board):
return tuple(tuple(r) for r in board)
def unmatched_cols(board, i, j):
r = []
for k in range(n):
if board[i][k] != board[j][k]:
return None
elif board[i][k] == 1:
r.append(k)
#print(board, i, j, r)
if len(r) == 0:
return None
if len(r) % 2 == 1:
return None
if sum(1 for k in r if k % 2 == 1) != sum(1 for k in r if k % 2 == 0):
return None
return r
def unmatched_rows(board, i, j):
r = []
for k in range(n):
if board[k][i] != board[k][j]:
return None
elif board[k][i] == 1:
r.append(k)
if len(r) == 0:
return None
if len(r) % 2 == 1:
return None
if sum(1 for k in r if k % 2 == 1) != sum(1 for k in r if k % 2 == 0):
return None
return r
def solve(board, goal):
board = [[abs(board[i][j] - goal[i][j]) for j in range(n)] for i in range(n)]
step = 0
cnt = 0
visited = set(encode(board))
while True:
if sum(sum(board[i]) for i in range(n)) == 0:
break
cnt += 1
rows = None
cols = None
for i in range(n):
for j in range(i+1, n, 2):
r = unmatched_rows(board, i, j)
if r is not None and (rows is None or len(rows) > len(r)):
rows = r
c = unmatched_cols(board, i, j)
if c is not None and (cols is None or len(cols) > len(c)):
cols = c
if cols is None and rows is None:
return -1
if rows is None or len(cols) < len(rows):
for i, j in zip([c for c in cols if c % 2 == 0], [c for c in cols if c % 2 == 1]):
for k in range(n):
board[k][i], board[k][j] = 1 - board[k][j], 1 - board[k][i]
step += 1
elif cols is None or len(rows) <= len(cols):
for i, j in zip([r for r in rows if r % 2 == 0], [r for r in rows if r % 2 == 1]):
for k in range(n):
board[i][k], board[j][k] = 1 - board[j][k], 1 - board[i][k]
step += 1
else:
return -1
t = encode(board)
if t in visited:
return -1
visited.add(t)
return step
if n % 2:
s = sum(sum(r) for r in board)
if s == n * n // 2:
goal = board1
elif s == n * n // 2 + 1:
goal = board2
else:
return -1
rows = [0, 0]
cols = [0, 0]
for i in range(n):
s = sum(board[i])
if s < n // 2 or s > n // 2 + 1:
return -1
r = sum(goal[i])
if s != r:
rows[i%2] += 1
s = sum(board[j][i] for j in range(n))
if s < n // 2 or s > n // 2 + 1:
return -1
r = sum(goal[j][i] for j in range(n))
if s != r:
cols[i%2] += 1
if rows[0] != rows[1] or cols[0] != cols[1]:
return -1
return rows[0] + cols[0]
else:
if any(sum(r) != n // 2 for r in board):
return -1
if any(sum(board[j][i] for j in range(n)) != n // 2 for i in range(n)):
return -1
ans = min(solve(board, board1), solve(board, board2))
return ans if ans < inf else -1
Expected behavior
My code that got accepted outputs 1, however, the correct answer should be -1.