//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Xây cầu

Nói đến Đà Nẵng không thể không nhắc đến dòng sông Hàn thơ mộng và cầu sông Hàn – cây cầu quay đầu tiên ở Việt Nam – niềm tự hào của người dân thành phố. Tuy nhiên trong tương lai, khi thành phố được mở rộng thì Đà Nẵng cần phải có thêm nhiều cây cầu bắc qua sông Hàn.

1 c c r r c c
2 c r r r r c c
3 c c r r r c c
4 c c c r r r r c
5 c c c r r c r c
6 c c r r c r c
7 c r r c c c
1 2 3 4 5 6 7 8 9

Hiện tại, bản đồ thành phố Đà Nẵng có thể được vẽ trên một lưới ô vuông gồm M dòng và N cột như hình vẽ. Các dòng của lưới được đánh số từ 1 đến M từ phía Bắc xuống phía Nam, các cột của lưới được đánh số từ 1 đến N từ phía Tây sang phía Đông. Dòng sông Hàn chảy từ phía Nam lên phía Bắc của bản đồ và chia thành phố làm 2 nửa. Biết rằng cả dòng sông và 2 nửa thành phố đều là các miền ô vuông liên thông không có lỗ thủng.

Dòng sông được biểu diễn bằng một miền các ô vuông kề với 2 cạnh phía Bắc và Nam của bản đồ. Các ô thuộc dòng sông được ký hiệu bởi ký tự ‘r’. Các ô vuông thuộc địa phận thành phố được ký hiểu bởi ký tự ‘c’, các ô không thuộc địa phận thành phố được ký hiệu bởi ký tự ‘-’.

Ủy ban nhân dân thành phố quyết định cho đến năm 2020, Đà Nẵng cần phải xây dựng không quá K cây cầu nối hai bờ sông. Mỗi cây cầu được định nghĩa như là một đoạn các ô liên tiếp trên một dòng có 2 đầu mút là 2 ô nước nằm ở phía trái nhất và phải nhất của dòng đó. 2 cây cầu được xem như là khác nhau nếu chúng nằm trên các dòng khác nhau. Ví dụ trên hình, các ô vuông được gạch chéo là 1 cây cầu phủ 3 ô thuộc sông và 1 ô thuộc thành phố trên dòng 5.

Bạn hãy giúp Ủy ban nhân dân thành phố xác định các vị trí sẽ xây cầu sao cho sau khi xây xong các cây cầu thì 2 nửa thành phố được nối liền và đường đi giữa 2 ô xa nhất thuộc thành phố là ngắn nhất. Biết rằng bạn chỉ có thể di chuyển từ một ô vuông thuộc thành phố đến một ô vuông kề cạnh với nó cũng thuộc thành phố hoặc thuộc một trong các cây cầu vừa xây dựng, khi đó độ dài đường đi giữa 2 ô bất kỳ là số ô ít nhất phải đi qua để từ ô này có thể đến được ô kia.

Input: BRIDGES.INP

  • Dòng thứ nhất ghi 3 số nguyên dương M, N và K là kích thước của bản đồ và số cây cầu tối đa cần xây dựng.
  • Dòng thứ i trong M dòng tiếp theo ghi xâu ký tự độ dài N biểu diễn dòng thứ i của bản đồ.

Output: BRIDGES.OUT

  • Dòng thứ nhất ghi số P là số cây cầu cần xây dựng.
  • Dòng thứ hai ghi P số nguyên dương là chỉ số hàng của các cây cầu sẽ được xây dựng.

Giới hạn:

  • 4 ≤ M, N ≤ 100
  • 1 ≤ K ≤ 10
  • Thời gian: 1 s/test
  • Bộ nhớ: 16 MB

Ví dụ:

BRIDGES.INP BRIDGES.OUT
4 5 1

crrrc

ccrrc

-crrc

ccrr-

1

2

( Với cách xây này, 2 ô xa nhất là 2 ô (5,1) và (1,5) )

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Danh mục

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

sunset

Detroit Night

White-winged Scoter | Macreuse à ailes blanches

More Photos

Thống kê

  • 95,281 lượt xem

%d bloggers like this: