백준
1.Python
import sys
from collections import deque
input = sys.stdin.readline
n, m, h = map(int, input().split())
ladder = [[0] * n for _ in range(h)]
for _ in range(m):
a, b = map(int, input().split())
ladder[a - 1][b - 1] = 1
ans = 4
def check():
for i in range(n):
k = i
for j in range(h):
if ladder[j][k]:
k += 1
elif k > 0 and ladder[j][k-1]:
k -= 1
if i != k:
return False
return True
def solve(cnt, x, y):
global ans
if ans <= cnt:
return
if check():
ans = min(ans, cnt)
return
if cnt == 3:
return
for i in range(x, h):
k = y if i == x else 0
for j in range(k, n-1):
if ladder[i][j]:
j += 1
else:
ladder[i][j] = 1
solve(cnt+1, i, j+2)
ladder[i][j] = 0
solve(0, 0, 0)
print(ans if ans < 4 else -1)
시간 감소
import sys
input = sys.stdin.readline
def check():
global n, h
for i in range(n):
y = i
for k in range(h):
y += ladder[k][y]
if y != i:
return False
return True
def dfs(index,cnt,limit):
global n, h, result
if limit == cnt:
if check():
result = limit
return
for ind in range(index, n*h):
x = ind // n
y = ind % n
if y == n - 1:
continue
if not ladder[x][y] and not ladder[x][y + 1]:
ladder[x][y] = 1
ladder[x][y+1] = -1
dfs(ind + 2,cnt + 1,limit)
if result != 4:
return
ladder[x][y] = 0
ladder[x][y + 1] = 0
n, m, h = map(int,input().split())
if m == 0:
print(0)
else:
result = 4
call = 0
ladder = [[0]*n for _ in range(h)]
for _ in range(M):
row,node = map(int, input().split())
ladder[row-1][node-1] = 1
ladder[row-1][node] = -1
if check():
print(0)
else:
for k in range(1,4):
dfs(0,0,k)
if result != 4:
break
if result != 4:
print(result)
else:
print(-1)
설명
N, M, H = list(map(int, input().split()))
map_list = [[0] * (N-1) for _ in range(H)]
total_move = 4
for _ in range(M):
a, b = list(map(int, input().split()))
map_list[a-1][b-1] = 1
def go():
for i in range(N):
x, y = 0, i
orig_y = y
while(True):
x, y = x+1, y
if x == H+1:
break
if x-1 >= 0 and y-1 >= 0 and map_list[x-1][y-1] == 1:
x, y = x, y-1
continue
if x-1 >= 0 and y < N-1 and map_list[x-1][y] == 1:
x, y = x, y+1
continue
if orig_y != y:
return False
return True
def solution(cnt, start, limit):
global total_move
if cnt == limit:
if go() == False:
return False
else:
if total_move > limit:
total_move = limit
return True
for i in range(start, H):
for j in range(N-1):
if map_list[i][j] == 1:
continue
if map_list[i][j] == 0:
if j-1 >= 0 and map_list[i][j-1] == 1:
continue
if j+1 <= N-2 and map_list[i][j+1] == 1:
continue
map_list[i][j] = 1
if solution(cnt+1, i, limit):
return True
map_list[i][j] = 0
for i in range(4):
flag = solution(0, 0, i)
if flag:
break
if total_move == 4:
print("-1")
else:
print(total_move)