Created
April 13, 2019 03:38
-
-
Save showyou/ce682390114b6ed68ce929cef1285093 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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