VTAVTA

cho ma trận A(m,n) điền 0 or 1.
tìm đường đi ngắn nhất để đến biên.
inp: A,m,n,x,y
out : l
vd:
inp:
m=4,n=4.:
mảng A:
1 1 1 0
1 0 0 1
0 0 0 0
1 1 0 0
x=2,y=2
out:
l=3

darling

bạn cho mình hỏi giá trị x,y là gì??? và khi out ra thì l đó sao mình chưa hiểu ví dụ bạn lắm.

__________________
http://it9x.co.cc

VTAVTA

x,y là vị trí xuất phát.
A[x,y]=0.
note:chỉ đi vào ô số 0.

minhngq

Dùng thuật toán loang theo chiều rộng hoặc dijtra (tên đại loại thế) là xong thôi.. Đâu có phức tạp gì đâu...

Cheers,

VTAVTA

bác nói rõ hơn đi
em chưa hiểu

minhngq

Lấy thuật toán loang theo chiều rộng cho đơn giản nhé.

1. Từ ô bắt đầu (trong trường hợp này là ô {2,2}) bắt đầu di chuyển ra các ô có thể đi được xung quanh theo 4 hướng trên ({1,2}), dưới ({3,2}), trái ({2,1}), phải ({2,3}). Ô có thể đi được là ô mà: hoặc là có giá trị = 0 trong ma trận ban đầu; hoặc là có giá trị = 0 trong bảng đánh dấu ở bên dưới. Từ các ô này lại đi tiếp theo 4 hướng cho đến khi ko đi được nữa.
2. Sử dụng 1 bảng đánh dấu có kích thước là mxn để đánh dấu các ô nào đã đi rồi (ký hiệu = 1) và chưa đi (ký hiệu = 0)
3. Sử dụng 1 bảng có kích thước mxn để đo khoảng cách ngắn nhất từ ô ban đầu đến ô đó (ví dụ đặt tên là BangKhoangCach với BangKhoangCach[2,2]=0). Giá trị khoảng cách của 1 vị trí {y,x} bất kỳ = min(các giá trị tại 4 ô lân cận) + 1. Trong vị trí của 1 ô ko đi được, bồ đặt 1 số cực lớn vào (ví dụ 10000).
4. Sau khi đã đi qua hết tất cả các ô có thể đi được trong bảng. Bồ chỉ cần tìm các ô biên xem ô nào có giá trị trong BangKhoangCach thấp nhất thì đó chính là đáp án. Còn nếu giá trị thấp nhất bằng hoặc lớn hơn số cực lớn đó (10000) thì là ko có đường đi.

Cheers