Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

HAOI6000 - HAOI 6000

Ngày nay, khi internet đã trở nên vô cùng phổ biến, các cuộc thi đều có xu hướng chuyển sang hình thức thi on-line, vừa tiết kiệm được chi phí, vừa thu hút được số lượng đông đảo thí sinh. HAOI (Hot Angel On the Internet – tạm dịch là Thiên thần xinh đẹp trên mạng) là một cuộc thi như vậy. Giống như những cuộc thi sắc đẹp bình thường, HAOI cũng bao gồm các vòng thi phụ: tài năng, trí tuệ, trang phục truyền thống… Sau đây là câu hỏi ở phần thi trí tuệ:

Một toà nhà hình chữ nhật được chia thành MxN ô vuông nhỏ. Ở mỗi ô vuông, người ta xây đúng một bức tường là một trong hai đường chéo của ô đó. Yêu cầu tìm đường đi nhanh nhất từ mặt phía Bắc tới mặt phía Nam của toà nhà mà không được đi ra ngoài toà nhà?

Xét ví dụ trong hình vẽ bên, có 3 đường đi khác nhau. Trong đó, đường 1 và 3 là ngắn nhất với độ dài 10.

Giả sử bạn gái của bạn đang tham gia HAOI. Bạn hãy lập trình một chương trình giải quyết câu hỏi trên trong thời gian cho phép để giúp đỡ cô ấy.

Dữ liệu

  • Dòng đầu tiên là hai số M, N.
  • MxN số tự nhiên tiếp theo (mỗi số cách nhau ít nhất một khoảng trống) miêu tả trạng thái các bức tường ở các ô (1,1), (1,2) … (1,N), (2,1), (2,2) … (M,N). Số 0 nếu bức tường nối đỉnh trái trên với phải dưới, số 1 nếu bức tường nối đỉnh trái dưới và phải trên của ô vuông.

Kết quả

  • In ra file HAOI.OUT hai số nguyên là độ dài đường đi ngắn nhất và số lượng đường đi có độ dài như vậy. Trong trường hợp không có đường đi nào, in ra một dòng chứa hai số 0 0.

Giới hạn

1 ≤ M, N ≤ 1000

Ví dụ

Dữ liệu
5 5
0 0 1 1 1 
1 1 0 0 0
0 0 1 1 1
1 1 0 0 0
0 0 0 1 1	

Kết quả
10 2

Được gửi lên bởi:VOJ Team
Ngày:2008-08-09
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ADA95 ASM32 BASH BF C CSHARP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN GOSU HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PERL PERL6 PHP PIKE PRLG-swi PYTHON PYPY RUBY RUST SCM guile SCM qobi SED ST WHITESPACE
Nguồn bài:HAOI 2008 - Day 2 - Author: Nguyễn Hoành Tiến

hide comments
2021-05-27 18:00:51
Tham khảo: https://vnspoj.github.io/problems/HAOI6000
2019-11-05 04:01:17
đệ tử của Thái pro tự tin 1 đấm ko ac
2019-11-05 04:00:31
trâu 4 vòng ac wtf ?? :D ??
2019-05-26 05:12:48
dfs 1 hit ac nha, dfs mà 70 là do dfs ko chuẩn :v
2019-05-21 15:36:03
dfs 70 bfs ac dù chả khác gì nhau :)
2017-05-29 10:39:52
code xong bài này não to hẳn :)
2016-03-13 13:18:09
Nguyên buổi chiều đc có 50đ =)))
2015-11-12 19:17:21 ChienTran
nhầm m thành n, mất 4 phát mới AC :'(
2015-11-09 17:27:16 White Shadow
1 đấm :|
2015-07-13 06:00:49 there's no salvation for me...
10 điểm của em rơi đâu mất rồi ;(((
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.