노랑색이 현 위치고
파랑색이 도달해야할 위치
검정색은 움직일 수 없는 벽이고
빨강색은 한쪽 방향으로 막힐때까지 움직일 수 있음
각각 1 2 3 4라고 가정했을 때 최단거리 구하는거임
입력)
2차원 배열
1 3 0 0 0
0 3 0 0 0
0 4 0 3 2
3 4 4 0 0
3 0 0 0 0
답) 10
파랑색이 도달해야할 위치
검정색은 움직일 수 없는 벽이고
빨강색은 한쪽 방향으로 막힐때까지 움직일 수 있음
각각 1 2 3 4라고 가정했을 때 최단거리 구하는거임
입력)
2차원 배열
1 3 0 0 0
0 3 0 0 0
0 4 0 3 2
3 4 4 0 0
3 0 0 0 0
답) 10
빨간색이 약간 얼음 타일 같은 거 말하는 거임?
동그라미
뭔진 모르겠는데 다익 ㄱ
걍 4방향 다익 돌리면 잘 되지 않을까
크기 작으면 bfs일듯
8아님?
01bfs - dc App
정보 : navigation between movable obstacles 이라는 NP 문제다
bfs돌리면서 빨간거 밟았을때 같은 방향으로 쭉 테이블갱신하면 되는거아닐까 구현만 좀 늘었네 - dc App