HAOI6000 - HAOI 6000
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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
- Người up: voj
- Nguồn bài: HAOI 2008 - Day 2 - Author: Nguyễn Hoành Tiến