Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
3. Thoát mê cung In E-mail
(1 vote)
Người viết: Ngô Minh Đức   
27/03/2008
Mê cung có dạng lưới ô vuông hình chữ nhật kích thước mxn, các dòng của lưới được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái sang phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Mỗi ô là một phòng. Vách ngăn giữa hai phòng hoặc giữa phòng với phần bên ngoài có thể có hoặc không có cửa thông nhau. Mê cung được mô tả bởi bản đồ số B là bảng mxn số nguyên, trong đó thành phần ở vị trí giao của dòng i với cột j là Bij (0 ≤ Bij ≤ 4) cho biết số vách ngăn có cửa của ô (i,j). Thời gian đi từ một ô sang ô bên cạnh hoặc ra ngoài là 1, nếu vách ngăn tương ứng có cửa.

Yêu cầu: Cho biết m, n, bản đồ số B và (u, v) – toạ độ một ô nào đó trong mê cung. Hãy xác định một cách đặt cửa cho các phòng đảm bảo thỏa mãn bản đồ B và thời gian T để thoát ra khỏi mê cung từ phòng (u, v) là ít nhất. Biết rằng dữ liệu bản đồ số B đảm bảo có ít nhất một cách đặt cửa để thoát ra ngoài.

Dữ liệu vào

  • Dòng đầu tiên chứa 4 số nguyên m, n, u và v.
  • Dòng thứ i trong m dòng sau chứa n số nguyên Bi1, Bi2,. . ., Bin.

Các số trên cùng một dòng được phân tách nhau bởi dấu cách.

Kết qủa

Đưa ra số nguyên T.

Hạn chế

  • Trong tất cả các test: 2 ≤ m, n ≤ 50.
  • Có 50% số lượng test với m, n ≤ 25.

Ví dụ

<strong>Dữ liệu mẫu</strong>
4 4 3 3
1 1 1 0
1 0 3 2
1 1 1 0
0 1 0 0
 
<strong>Kết qủa</strong>
3
 
< Trước   Tiếp >