자율주행 전기차

자율주행 전기차를 이용해서 택시 업무를 진행하고자 합니다. 하지만 현재 사용하는 자율주행 전기차는 베타테스트 버전이기 때문에 배터리 양이 모두 소진되는 경우 더이상 움직일 수 없습니다. 테스트를 위해 n×n 격자의 도로 위에 차가 지나갈 수 없는 벽의 위치와 m명의 승객의 위치가 주어질 때 주어진 배터리 용량으로 승객을 모두 태워줄 수 있는지를 알아보고자 합니다.

자율주행 전기차는 승객을 태우러 출발지에 이동할 때에나 태우고 목적지로 이동할 때 항상 최단 거리로 이동합니다.