14923번 - 미로 탈출
이 문제를 해결하기 위해 dp를 이용하여 풀려고했습니다.
최종목적지로 가기전에 최소의 경우의 수는 항상
그 전 도착지의 최소의 경우의 수 + 1이니까요.
그리고 마법을 한번 쓸 수 있다고 했기 때문에 그것도 처리해준거같아요.
하지만 무엇이 잘못되었는지 잘모르겠습니다.
분명한것은 반례 케이스가
5 61 15 6
0 1 1 1 0 00 1 1 0 0 00 1 0 0 1 00 1 0 0 1 00 1 0 0 0 0
있는데 왜 안되는지 잘모르겠습니다 .ㅠ.ㅠ
도움부탁드립니다..
d[x][y]는 마법을 사용했는지의 여부에 아무 정보도 주지 않습니다.
그리고 이런 최단거리 문제를 DFS로 푸는 것은 좋지 않습니다. BFS를 사용해 보세요.
@jh05013 90% 거의 다 이해하고 푼것 같습니다 감사합니다 ㅠ.ㅠ
댓글을 작성하려면 로그인해야 합니다.
gaelim 6년 전
이 문제를 해결하기 위해 dp를 이용하여 풀려고했습니다.
최종목적지로 가기전에 최소의 경우의 수는 항상
그 전 도착지의 최소의 경우의 수 + 1이니까요.
그리고 마법을 한번 쓸 수 있다고 했기 때문에 그것도 처리해준거같아요.
하지만 무엇이 잘못되었는지 잘모르겠습니다.
분명한것은 반례 케이스가
5 6
1 1
5 6
0 1 1 1 0 0
0 1 1 0 0 0
0 1 0 0 1 0
0 1 0 0 1 0
0 1 0 0 0 0
있는데 왜 안되는지 잘모르겠습니다 .ㅠ.ㅠ
도움부탁드립니다..