Bài 1 : Súc sắc
Nhân ngày thành lập công ty Mycrosoft , Bill Gate đã cho các
nhân viên của mình đuợc nghỉ và tổ chức tiệc chiêu đãi .
Trong buổi tiệc , có tổ chức một trò chơi nhỏ cho mọi người ,
trò chơi như sau :
Cho một hình chữ nhật có kích thước MxN , mỗi ô của bảng
là một ô vuông chứa một số nguyên có giá trị từ 1 đến 6 .
Khi trò chơi bắt đầu , tại ô (x,y) của bảng , đặt một súc sắc
hình lập phương có cạnh đúng băng cạnh một ô vuông trong
bảng , súc sắc có 6 mặt chứa 6 số nguyên khác nhau từ 1
đến 6 sao cho 2 mặt đồi nhau của súc sắc có tổng bằng 7 .
Yêu cầu của trò chơi , là từ vị trí (x,y) hãy tìm cách lăn súc
sắc ra khỏi hàng với số lần lăn súc sắc là ít nhất . BIẾT
rằng , súc sắc chỉ có thể lăn trong 4 ô kề cạnh nếu như sau
khi lăn mặt đáy của súc sắc có giá trị trùng với giá trị của ô
mới .
Yêu cầu : hãy viết chương trình tìm tất cả các cách lăn súc
sắc ra khỏi hàng với số lân lăn ít nhất .
Dữ liệu : từ file SUCSAC.INP gồm nhiều dòng :
- Dòng đầu tiên chứa 2 số nguyên M,N ( M,N <=30)
- M dòng tiếp theo mỗi dòng chứa N số nguyên ( có giá trị từ
1 --> 6 )
- Dòng tiếp theo chứa 2 số nguyên x và y , vị trí xuất phát
của súc sắc lúc bắt đầu trò chơi .
- Dòng cuối cùng chứa 3 số nguyên , lần luợt là giá trị của
mặt trên , mặt trước , mặt phải của súc sắc tại vị trí x ,y bàn
đầu .
Kết quả : ghi ra file SUCSAC.OUT :
- Dòng đầu tiên là số nguyên K : số bước lăn ít nhất tìm
đuợc ( k = -1 nếu ko thể lăn ra khỏi bảng đuợc )
- Dòng tiếp theo ( chỉ ghi trong trường hợp tồn tại cách lăn )

Yêu cầu : hãy giúp Thành Đoàn tìm điểm hội quân có chi phí
thấp nhất .
Dữ liệu vào : từ file HOIQUAN.INP gồm nhiều dòng :
- Dòng đầu tiên số N ( N <= 30 )
- N dòng tiếp theo mỗi dòng chứa N số nguyên không âm .
Số nguyên thứ j là chi phí từ i đến j ( nếu = 0 là không có
đường đi từ i đến j )
(tên quận huyện là số nguyên từ 1 đến N )
Kết quả : ghi ra file HOIQUAN.OUT có thể gồm nhiều dòng :
- dòng đầu tiên chứa số nguyên S : chi phí của điểm hội
quân có chi phí thấp nhất . ( S = -1 , nếu ko tìm đuợc điểm
hội quân tốt nhất )
- Dòng tiếp theo chứa số nguyên Q : số luợng quận huyện
có thể được chọn
- Dòng cuối cùng chứa Q số nguyên : dánh sách các quận
huyện có thể đuợc chọn là địa điểm hội quân ( ghi theo thứ
tự tăng dần ) .
Ví dụ :
HOIQUAN.INP
5
0 2 1 2 0
0 0 0 3 0
0 2 0 0 3
0 0 0 0 1
0 0 0 2 0
HOIQUAN.OUT
4
1
5