Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import copy
T = int(input())
def find_warp(galaxy, y, x, R, C):
#print("find_warp", y, x, galaxy)
# pick up next warp which is
# x != x2
# y != y2
# x - y != x2 - y2
# x + y != x2 + y2
def is_ok(x, y, x2, y2):
if x == y == 0:
return True
if (x - y != x2 - y2) and (x + y != x2 + y2):
return True
return False
def check_galaxy(galaxy, R, C):
for i in range(1,R+1):
for j in range(1,C+1):
if galaxy[i][j] == 0:
return False
return True
if check_galaxy(galaxy, R, C):
return []
for i in range(1,R+1):
if i == y:
continue
for j in range(1,C+1):
if j == x:
continue
if is_ok(y, x, i, j) and galaxy[i][j] == 0:
galaxy2 = copy.deepcopy(galaxy)
galaxy2[i][j] = 1
result = find_warp(galaxy2, i, j, R, C)
if result != False:
result.append((i, j))
return result
return False
for cnt in range(T):
R, C = map(int, input().split())
galaxy = [[0 for _ in range(C+1)] for _ in range(R+1)]
result = find_warp(galaxy, 0, 0, R, C)
if result == False:
print("Case #"+str(cnt+1)+": IMPOSSIBLE")
else:
print("Case #"+str(cnt+1)+": POSSIBLE")
for res in result:
print(res[0], res[1])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.