30/09/2018, 19:06
Robot tìm đường
Ban đầu robot được đặt ở vị trí (0, 0) (nằm ở vị trí trên cùng bên trái). Và chú robot tự tìm đường đi đến vị trí đích (là ô dưới cùng bên tay phải (tọa độ (m-1, n-1)). Biết rằng chú chỉ có thể đi xuống hoặc qua phải và trong mê cung có một số ô đặc biệt robot không được phép đi vào
Hỏi có bao nhiêu cách đi từ vị trị đầu đến vị trí đích ?
Input:
Dòng đầu tiên chứa 3 số nguyên m, n, k (0< m,n<=100 và k< m*n) k dòng tiếp theo, mỗi dòng chứa hai số nguyên x, y với (x, y) là tọa độ của ô đặc biệt robot không được phép đi vào
output
Số cách đi từ vị trí xuất phát đến vị trí đích
EX:
input
3 7 2
1 1
1 3
output
8
giúp em với. em cám ơn trước
Bài liên quan
Bạn sử dụng phương án quy hoạch động nhé.
+Số cách đi từ ô bắt đầu đến ô [x,0] là f[x,0]=1;
+Số cách đi từ ô bắt đầu đến ô [0,x] là f[0,x]=1;
+Số cách đi từ ô bắt đầu đến ô [x,y] là f[x,y]=f[x-1,y]+f[x,y-1];
www.giaosudauto.blogspot.com
làm được rồi cảm ơn bạn nha
Bạn đánh dấu câu trả lời đúng đi.