#21. HY014 - Di chuyển Robot

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Một sân chơi có kích thước n\times n ( n lẻ) được chia thành lưới n\times n ô vuông (các dòng được đánh số từ 1 tới n , các cột được đánh số từ 1 đến n ). Ô vuông chính giữa là vị trí đích. Ở một số ô khác có các robot khác nhau. Mỗi lần, một robot chỉ có thể thực hiện hoặc chuyển động đến ô bên cạnh chung cạnh mất 10 đơn vị năng lượng hoặc chuyển động đến ô bên cạnh chung đỉnh mất 15 đơn vị. Các robot có thể đi vào các thời điểm khác nhau và đi vào ô robot khác đã đi qua. Hãy tính xem chi phí tối thiểu để chuyển các robot trên về đích là bao nhiêu?

Dữ liệu:

  • Dòng đầu tiên ghi n\ (n≤100) ;
  • Dòng thứ hai ghi K là số robot (K≤100) ;
  • K dòng tiếp theo, mỗi dòng ghi hàng và cột của một robot.

Kết quả:

  • Một số nguyên duy nhất là tổng năng lượng ít nhất để chuyển các robot đến ô đích.

Ví dụ:

Dữ liệu:

5
2
1 1
2 3

Kết quả:

40