Tất cả các lối đi trong mê cung
Một mê cung kích thước \(n*m\) chỉ chứa các số \(0\) và \(1\) là một ma trận \(n\) hàng đánh chỉ số từ \(1\) đến \(n\) theo chiều từ trên xuống và \(m\) cột đánh chỉ số từ \(1\) đến \(m\) từ trái sang phải
Một con rùa xuất phát từ vị trí \(1,1\) muốn đi đến vị trí \(n*m\) trong đó chỉ những ô số chứa số 0 thì đi được còn ô chứa số 1 thì không đi được (hai vị trí xuất phát và đích đều là \(0\)).
Mỗi bước rùa chỉ bò sang được trong 4 ô láng giềng và không đi ra ngoài ma trận. Bạn hãy chỉ tất cả các đường di để con rùa đi tới đích theo các hướng D, T, N, B tương ứng với Đông Tây Nam Bắc
Các kết quả xếp ra nếu có nhiều kết quả thì xuất theo thứ tự từ điển mỗi kết quả một dòng biết rằng:
- Sang trái là hướng Tây T
- Sang phải là hướng Đông D
- Xuống dưới là hướng Nam N
- Lên trên là hướng Bắc B
Trong đó thứ tự từ điển là \(B < D < N < T\)
Input
Dòng đầu chứa hai số nguyên dương \(n,m (1 \le n,m \le 30)\)
Tiếp theo lần lượt \(n\) hàng mỗi hàng \(m\) cột của ma trận chỉ chứa các số \(0\) và \(1\)
Ouput
Các xâu chỉ ra cách đi của con rùa được xếp theo thứ tự từ điển, trong trường hợp không tồn tại cách đi xuất ra rua khong di duoc
Ví dụ
Input
5 7
0 1 1 0 0 1 0
0 0 0 0 0 1 0
1 0 1 1 0 0 0
0 0 0 0 0 1 0
1 0 1 1 0 1 0Output
NDDDBDNNDDNN
NDDDDNDDNN
NDNNDDDBDDNN
Comments
Thầy ơi bài này phải là sang trái là hướng Tây, sang phải là hướng Đông mới đúng
Thanks, Thầy đã sửa
cho e xin 2 test case cuối với ạ :)
Thầy đã kiểm tra lại, lỗi do bộ test của thầy, thầy sẽ up lại