bài toán đường đi của rô bốt:

H

hai6f2009

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Bài 3 : Đường đi của Robot

Cho một bảng vuông (n x n) ô (2<=n<=100) các ô ghi các số là 0 hoặc 1. Tìm đường đi của Robot, từ góc trái trên xuống góc phải dưới theo nguyên tắc chỉ được dịch chuyển sang phải và xuống dưới sao cho các số trên đường đi tạo thành một số nhị phân có giá trị lớn nhất.
Dữ liệu vào : ghi trong tập tin văn bản ROBOT.INP gồm
- Dòng đầu tiên ghi giá trị
- n dòng tiếp theo, trên mỗi dòng ghi n số 0 hoặc 1 các số này cách nhau ít nhất một khoảng trắng.
Dữ liệu ra : Ghi vào tập tin văn bản ROBOT.OUT gồm một số duy nhất là giá trị thập phân của số nhị phân được tạo thành ở trên.
Ví dụ :
ROBOT.INP
5
1 0 1 1 0
0 0 1 0 1
0 0 1 0 1
1 0 0 1 1
1 1 0 1 0
ROBOT.OUT
374
 
T

thienvamai

bài này buớc 1 là phải cấu hình số lớn :3, tạm nghĩ đuợc đến thế
 
H

hai6f2009

mình nghĩ nó là quy hoạch động nhưng nghĩ mãi chưa ra công thức. chán~X(9;!:(
 
E

englandhuynh

Mình nghĩ được thuật này :
- Mảng a để lưu bảng vuông + 2 Mảng x,y để lưu vị trí của phần tử
- Viết 1 hàm GTTT để tìm giá trị tiếp theo trong đường đi : Có 2 trường hợp
+ Mảng x,y đều có 1 phần tử
___ Nếu a[x[1]+1,y[1]] <> a[x[1],y[1]+1] thì GTTT:=max(a[x[1]+1,y[1]] <> a[x[1],y[1]+1]); cập nhật x[1] và y[1]
___ Ngược lại thì thêm 2 vị trí này vào mảng x,y thế cho vị trí cũ
+ Mảng x,y có nhiều phần tử
___ Nếu có vị trí nào mà có vị trí khác trong mảng x,y có vị trí bên phải hoặc ở dưới lớn hơn thì loại bỏ phần tử đó ra khỏi mảng x,y
___ Sau bước này thì thay mỗi vị trí trong mảng x,y thành 2 vị trí bên phải và phía dưới nó.
___ Nếu có vị trí nào bằng 1 thì loại bỏ hết các vị trí = 0
___ GTTT := a[x[1],y[1]]
 
M

mikelhpdatke

Bài này QHD.
F[i,j] là quãng đường max khi đi đến oo A[i,j].
F[i,j]:=Max(F[i-1,j]+A[i,j],F[i,j-1]+A[i,j])

Theo mình nên xử lý xâu cho đơn giản nhé :)
 
H

hai6f2009

vậy chỗ mảng a mình khai báo là char hay string vậy bạn? Có cần bao ngoài hay không? Nếu có thì bao ngoài như thế nào?
 
You must log in or register to reply here.
Top Bottom