toj 2696 Collecting Beepers
2965 단어 in
Collecting Beepers
Time Limit: 1.0 Seconds
Memory Limit: 65536K
Karel is a robot who lives in a rectangular coordinate system where each place is designated by a set of integer coordinates (x and y). Your job is to design a program that will help Karel pick up a number of beepers that are placed in her world. To do so you must direct Karel to the position where each beeper is located. Your job is to write a computer program that finds the length of the shortest path thatwill get Karel from her starting position, to each of the beepers, and return back again to the starting position. Karel can only move along the x and y axis, never diagonally. Moving from one position (i, j) to an adjacent position (i, j+1), (i, j-1), (i-1,j), or (i+1, j) has a cost of one. You can assume that Karel's world is never larger than 20 × 20 squares and that there will never be more than 10 beepers to pick up. Each coordinate will be given as a pair (x, y) where each value will be in the range 1 through the size of that particular direction of the coordinate system.
Input specifications
First there will be a line containing the number of scenarios you are asked to help Karel in. For each scenario there will first be a line containing the size of the world. This will be given as two integers (x-size and y-size). Next there will be one line containing two numbers giving the starting position of Karel. On the next line there will be one number giving the number of beepers. For each beeper there will be a line containing two numbers giving the coordinates of each beeper.Output specifications
The output will be one line per scenario, giving the minimum distance that Karel has to move to get from her starting position to each of the beepers and back again to the starting position.Sample input
1
10 10
1 1
4
2 3
5 5
9 4
6 5
Output for sample input
The shortest path has length 24
Source: Nordic Collegiate Contest 2002
Problem ID in problemset: 2696
Submit Back Runs Statistics Clarifications
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
SQL Day 1_DB, My SQL파이썬 과정이 끝나고 SQL과정 첫 날이었다. 파이썬보다 환경설정에서 까다로웠지만 MySQL로 어떤 활용을 할 수 있는지 감은 잡힌 거 같다. 파이썬의 BeatifulSoup과 Selenium으로 크롤링을 해온 자료...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.