[질문] 2×N 격자판에서 두 점의 최단거리

[익명(218.54)]

를 모든 점에 다익스트라 돌려서 O(N^2lgN) 전처리하는 것보다 빠르게 구하는 방법 있음?
DP쓰면 엔제곱 나올 것 같은데 생각하기가 넘 귀찮다 ㅁㄴㅇㄹ

[익명(203.226)]

x좌표 차이 + y좌표 차이잖아 바보야 - dc App

[익명(223.62)]

당연히 장애물이 있지않을까

[이 댓글은 게시물 작성자가 삭제하였습니다.]

이 댓글은 게시물 작성자가 삭제하였습니다.

[익명(218.54)]

장애물 있고 3방향으로 가중치 있는 간선 있음 (모서리는 2개)

[익명(203.226)]

그러면 가로로 좌표 차이 + 그 사이에 있는 장애물 개수가 답이 아닐까싶은데. 물론 장애물 2개인 칸있으면 안되고 장애물 최대 1개 - dc App

[익명(203.226)]

장애물 두개인 칸이 아니라.. 열 - dc App

[익명(218.54)]

장애물만 있으면 모르겠는데 가중치가 문제라서..

[0xrgb(0xrgb)]

가중치 음수 없으면 DP

[익명(218.54)]

ㄱㅅ

[익명(218.54)]

ㅈㅅ 전혀 DP 어케 할지 생각이 안 나는데 힌트좀