Strict Standards: call_user_func_array() expects parameter 1 to be a valid callback, non-static method HTML_content::show() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/Cache/Lite/Function.php on line 98

Strict Standards: Non-static method HTML_content::_Itemid() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 452

Strict Standards: Non-static method HTML_content::_linkInfo() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 455

Strict Standards: Non-static method SAXY_Parser_Base::parseAttributes() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/mambots/content/geshi.php on line 57

Strict Standards: Non-static method HTML_content::Title() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 470

Strict Standards: Non-static method HTML_content::PdfIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 473

Strict Standards: Non-static method mosHTML::PrintIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 476

Strict Standards: Non-static method mosAdminMenus::ImageCheck() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/joomla.php on line 2329

Strict Standards: Non-static method HTML_content::EmailIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 479
3. Thoát mê cung
Strict Standards: Non-static method HTML_content::EditIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 632

Strict Standards: Non-static method HTML_content::Section_Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 511

Strict Standards: Non-static method HTML_content::Section() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 755

Strict Standards: Non-static method HTML_content::Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 758

Strict Standards: Non-static method HTML_content::Author() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 514

Strict Standards: Non-static method HTML_content::CreateDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 517

Strict Standards: Non-static method HTML_content::URL() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 520

Strict Standards: Non-static method HTML_content::ModifiedDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 536

Strict Standards: Non-static method HTML_content::ReadMore() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 539
Người viết: Ngô Minh Đức   
27/03/2008

Strict Standards: Non-static method HTML_content::TOC() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 526
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
 
Strict Standards: Non-static method HTML_content::Navigation() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 550

Strict Standards: Non-static method mosHTML::CloseButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 553

Strict Standards: Non-static method mosHTML::BackButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 556