Sau một ngày dài luyện tập APIO mệt mỏi, Alice và Bob quyết định ra chợ đêm để ăn tối. Vì đang thèm bánh quy, hai người tìm đến một khu chợ đêm đặc biệt — nơi mỗi quầy hàng đều bán bánh quy có hình dạng các chữ số.

Khu chợ đêm được bố trí theo dạng lưới \(N \times M\), các hàng được đánh số \(0, 1, \ldots, N-1\) từ bắc xuống nam, các cột được đánh số \(0, 1, \ldots, M-1\) từ tây sang đông. Ký hiệu \((i, j)\) là ô nằm trên hàng thứ \(i\) và cột thứ \(j\). Tại mỗi ô \((i, j)\) với \(0 \le i \le N-1\) và \(0 \le j \le M-1\), có đúng một quầy bán bánh quy mang hình dạng một chữ số từ \(0\) đến \(9\), ký hiệu là \(S[i][j]\).

Do lượng khách du lịch đông đúc, khu chợ áp dụng các quy định sau để giữ trật tự:

• Tất cả du khách phải vào chợ từ ô \((0, 0)\) và rời chợ tại ô \((N-1, M-1)\).
• Khi đứng tại ô \((i, j)\), du khách phải mua đúng một chiếc bánh hình \(S[i][j]\) từ quầy tại đó. Sau khi mua, họ phải di chuyển đến ô \((i+1, j)\) hoặc \((i, j+1)\). Nếu ô đó không tồn tại, họ không được chọn hướng đó. Đặc biệt, nếu \((i, j) = (N-1, M-1)\), du khách phải rời chợ sau khi mua bánh.

Như vậy, mỗi du khách sẽ mua đúng \(N + M - 1\) chiếc bánh trước khi rời chợ.

Alice và Bob tự hỏi liệu có cách nào để họ đi theo hai chuỗi ô khác nhau nhưng mua được cùng một chuỗi hình dạng bánh quy hay không. Hai chuỗi ô được gọi là khác nhau nếu tồn tại ít nhất một vị trí mà ô tại vị trí đó trong hai chuỗi không trùng nhau.

Cho thông tin về hình dạng bánh quy tại từng quầy, hãy viết chương trình tìm hai chuỗi ô khác nhau thỏa mãn điều kiện trên, hoặc thông báo rằng không có nghiệm.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau trong file nightmarket.h:

std::vector<std::string> find_sequences(int N, int M,
    std::vector<std::vector<int>> S)

• \(N\): số hàng.
• \(M\): số cột.
• \(S\): mảng hai chiều kích thước \(N \times M\), trong đó \(S[i][j]\) là hình dạng bánh quy tại quầy ô \((i, j)\).
• Hàm này được gọi đúng một lần cho mỗi test case.

Hàm cần trả về một mảng \(P\) có độ dài \(0\) hoặc \(2\).

• Nếu không có nghiệm, \(P\) phải là mảng rỗng.
• Ngược lại, \(P\) phải chứa hai xâu \(P[0]\), \(P[1]\) có độ dài \(N + M - 2\), mô tả hai chuỗi ô.
• Mỗi xâu phải chứa đúng \(N-1\) ký tự S (đi xuống) và \(M-1\) ký tự E (đi sang phải).
• Định nghĩa chuỗi ô thứ nhất \((A[0], B[0]),\ (A[1], B[1]),\ \ldots,\ (A[N+M-2], B[N+M-2])\) như sau:
  • \((A[0], B[0]) = (0, 0)\).
  • Với \(0 \le i \le N+M-3\): nếu \(P[0][i]\) là S thì \((A[i+1], B[i+1]) = (A[i]+1, B[i])\); nếu là E thì \((A[i+1], B[i+1]) = (A[i], B[i]+1)\).
• Tương tự, định nghĩa chuỗi ô thứ hai \((C[0], D[0]),\ \ldots,\ (C[N+M-2], D[N+M-2])\) theo \(P[1]\).
• Phải tồn tại \(i\) với \(0 \le i \le N+M-2\) sao cho \((A[i], B[i]) \ne (C[i], D[i])\).
• Với mọi \(0 \le i \le N+M-2\), phải có \(S[A[i]][B[i]] = S[C[i]][D[i]]\).

Ràng buộc

• \(2 \le N, M \le 1000\)
• \(0 \le S[i][j] \le 9\) với mọi \(0 \le i < N\) và \(0 \le j < M\).

Phân nhóm

• Subtask 1 (5 điểm): \(N, M \le 8\).
• Subtask 2 (15 điểm): \(N = 2\).
• Subtask 3 (80 điểm): Không có ràng buộc thêm.

Ví dụ

Ví dụ 1

find_sequences(2, 4, [[1, 2, 3, 4], [5, 3, 4, 5]])

Một nghiệm có thể là:

• Chuỗi 1: \((0,0) \to (0,1) \to (0,2) \to (0,3) \to (1,3)\)
• Chuỗi 2: \((0,0) \to (0,1) \to (1,1) \to (1,2) \to (1,3)\)

Dãy hình dạng bánh quy của cả hai chuỗi đều là \([1, 2, 3, 4, 5]\).

Hàm có thể trả về: ["EEES", "ESEE"].

Giải thích: Hai người xuất phát cùng tại \((0,0)\) mua bánh số \(1\), rồi cùng sang \((0,1)\) mua bánh số \(2\). Sau đó Alice tiếp tục đi sang \((0,2) \to (0,3)\) rồi xuống \((1,3)\); Bob rẽ xuống \((1,1)\) rồi đi sang \((1,2) \to (1,3)\). Dù đi khác đường, hai người mua cùng dãy hình \([1,2,3,4,5]\).

Ví dụ 2

find_sequences(3, 3, [[1, 2, 3], [4, 5, 6], [7, 8, 9]])

Không có nghiệm, hàm trả về mảng rỗng.

Giải thích: Tất cả các chữ số trong lưới đều khác nhau, nên không thể tìm được hai đường đi tạo ra cùng dãy hình dạng bánh.

Chấm điểm

Với mỗi test case, định nghĩa \(W\) như sau:

• Nếu không có nghiệm:
• Nếu trả về mảng rỗng: \(W = 1\).
• Nếu trả về mảng không rỗng: \(W = 0\).
• Nếu có ít nhất một nghiệm:
• Nếu mảng trả về thỏa mãn tất cả điều kiện trong phần chi tiết cài đặt: \(W = 1\).
• Nếu mảng trả về không thỏa mãn điều kiện, nhưng chứa đúng hai xâu gồm đúng \(N-1\) ký tự S và \(M-1\) ký tự E: \(W = 0.5\).
• Ngược lại: \(W = 0\).

Với mỗi subtask, gọi \(W_{\min}\) là giá trị \(W\) nhỏ nhất trên tất cả test case và \(S\) là điểm tối đa của subtask đó, bạn nhận được \(S \times W_{\min}\) điểm cho subtask đó.