245.操作はしご
34086 ワード
白駿
1.Python
import sys
from collections import deque
input = sys.stdin.readline
#n: 열, h:행
n, m, h = map(int, input().split())
ladder = [[0] * n for _ in range(h)]
for _ in range(m):
#a:행, b:열
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]: #사다리가 연결되어 있다면 (i, j+2)
j += 1
else:
ladder[i][j] = 1 #사다리 만들기
solve(cnt+1, i, j+2) #(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
#1번부터 시작해서 1번에 1번, 2번에 2번,,, 이 맞나 확인하는 메소드
def go():
for i in range(N):
x, y = 0, i #출발 좌표 저장
orig_y = y #나중에 맞나 비교를 위해 원래 좌표 저장
while(True):
#down
x, y = x+1, y
if x == H+1:
break
#check left
if x-1 >= 0 and y-1 >= 0 and map_list[x-1][y-1] == 1:
x, y = x, y-1
continue
#check right
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:
#사다리 타봤는데 1번째에 1번이 안나온다면
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
#나의 맵에다가 1을 넣어주고(다리가 놓여져있다)
map_list[i][j] = 1
#다리를 마지막으로 놨던 행부터 다시 시작
if solution(cnt+1, i, limit):
return True
#백트래킹의 방법
map_list[i][j] = 0
#다리 0개부터 돌려보자
for i in range(4):
flag = solution(0, 0, i)
if flag:
break
if total_move == 4:
print("-1")
else:
print(total_move)
#출처: https://coreenee.github.io/2020/07/02/%EB%B0%B1%EC%A4%8015684(%EC%82%AC%EB%8B%A4%EB%A6%AC-%EC%A1%B0%EC%9E%91)/
Reference
この問題について(245.操作はしご), 我々は、より多くの情報をここで見つけました https://velog.io/@corone_hi/245.-사다리-조작テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol