bàn cờ!!!!!

[active_boy2701]

cho 1 bàn cờ 8*8, có những con cờ được xếp bên trong. Hãy tìm dãy các con cờ mà có độ dài lớn nhất.


VD:
tập inp:
0 1 0 1 0 1 0 0
1 0 0 1 1 0 0 1
1 0 1 0 0 0 1 1
0 0 0 1 0 1 0 0
0 0 1 0 0 0 0 0
0 1 0 1 0 0 0 1
1 0 0 1 1 0 0 0
0 1 0 0 0 1 1 0
tập out:11

[truongngocdai]

dùng BFS hoặc DFS, đánh dấu từng ô đã đi qua. Duyệt 64 lần (nhưng đã đánh dấu nên rất nhanh)

[Master_Baby]

Liệu có đánh dấu đúng ko:
0 0 1
0 0 1
1 1 1
Chẳng hạn đã xét hàng 1 dọc phải rồi, đánh dấu hết rồi, khi xét đến hàng 1 ngang dưới thì có đếm đủ?

[truongngocdai]

n=8
for i:=1 to n do
for j:=1 to n do
if free[i,j] then DFS/BFS(i,j);

[active_boy2701]

DFS và BFS là hàm gì vậy??????
theo tôi, bài này giải được bằng quy hoạch động

[truongngocdai]

DFS và BFS là thuật toán duyệt trong đồ thị
bài này ko cần giải bằng quy hoạch động mà nếu dùng QHĐ thì tôi cũng ko biết dùng thế nào

[Master_Baby]

D chắc là deep? Còn B thì là best?

[truongngocdai]

sai rồi, D đúng là deep nhưng B là Breath
DFS: là tìm kiếm sau
BFS: là tìm kiếm rộng
còn có BestFS nhưng cách cài đặt khá khó

[Rikku]

D = Depth
Br = Breadth
B = Best

[truongngocdai]

à há, trước kia em học thì
D = Depth
B = Breadth
còn Best thì ... , em biết nhưng chưa học