Tất cả các lối đi trong mê cung

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

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:

  1. Sang trái là hướng Tây T
  2. Sang phải là hướng Đông D
  3. Xuống dưới là hướng Nam N
  4. 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≤n,m≤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

Copy
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   0

Output

Copy
NDDDBDNNDDNN
NDDDDNDDNN
NDNNDDDBDDNN
tichpx

Comments


  • 0
    Phuc_CNTT3_K60  commented on July 8, 2020, 6:37 a.m.

    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


    • 1
      TICHPX  commented on July 8, 2020, 6:42 a.m.

      Thanks, Thầy đã sửa


  • 2
    Giang_CNTT3_K60  commented on June 11, 2020, 10:00 a.m.

    cho e xin 2 test case cuối với ạ :)


    • 1
      TICHPX  commented on June 12, 2020, 3:12 a.m.

      Thầy đã kiểm tra lại, lỗi do bộ test của thầy, thầy sẽ up lại