Đề bài
Một nhà thiết kế sân khấu điều khiển một bảng đèn hình chữ nhật. # là đèn đang bật và . là đèn đang tắt. Bấm một đèn sẽ đảo trạng thái của nó cùng bốn đèn kề bên (trên, dưới, trái, phải), nếu những đèn đó có trên bảng. Hãy xử lý lần lượt các thao tác sau:
toggle r c: bấm đèn ở hàngr, cộtc(không cho kết quả).count: cho kết quả là số đèn đang bật.row r: cho kết quả là số đèn đang bật trong hàngr.col c: cho kết quả là số đèn đang bật trong cộtc.status r c: cho kết quả 1 nếu đèn đó đang bật, ngược lại cho 0.
Hàng và cột được đánh số từ 0, và mọi chỉ số đều nằm trên bảng.
Hãy viết light_board(board, operations).
Đầu vào
board: Bảng ban đầu, mỗi hàng là một chuỗi; mọi hàng có cùng độ dài.
operations: Các thao tác, xử lý theo thứ tự.
Đầu ra
Trả về kết quả của count, row, col và status theo thứ tự chúng xảy ra.
Ràng buộc
1 ≤ rows, cols ≤ 50
0 ≤ số thao tác ≤ 1,000
Ví dụ
Đầu vào:
board = ["...", "...", "..."]
operations = ["toggle 1 1", "count", "row 0", "status 0 0"]
Kết quả mong đợi:
expected = [5, 1, 0]
Đầu vào:
std::vector<std::string> board = {"...", "...", "..."};
std::vector<std::string> operations = {"toggle 1 1", "count", "row 0", "status 0 0"};
Kết quả mong đợi:
std::vector<long long> expected = {5, 1, 0};
Đầu vào:
string[] board = new string[] {"...", "...", "..."};
string[] operations = new string[] {"toggle 1 1", "count", "row 0", "status 0 0"};
Kết quả mong đợi:
long[] expected = new long[] {5, 1, 0};
Giải thích
Bấm đèn chính giữa làm sáng 5 đèn thành hình dấu cộng. Hàng 0 chỉ có đèn ở giữa bật, còn góc (0, 0) vẫn tắt: [5, 1, 0].
Đầu vào:
board = ["#.", "##"]
operations = ["toggle 0 0", "count", "col 1", "status 1 1"]
Kết quả mong đợi:
expected = [2, 2, 1]
Đầu vào:
std::vector<std::string> board = {"#.", "##"};
std::vector<std::string> operations = {"toggle 0 0", "count", "col 1", "status 1 1"};
Kết quả mong đợi:
std::vector<long long> expected = {2, 2, 1};
Đầu vào:
string[] board = new string[] {"#.", "##"};
string[] operations = new string[] {"toggle 0 0", "count", "col 1", "status 1 1"};
Kết quả mong đợi:
long[] expected = new long[] {2, 2, 1};
Giải thích
Bấm ở góc đảo trạng thái các đèn (0, 0), (1, 0) và (0, 1): bảng trở thành .# / .#, nên có 2 đèn bật, cả hai đều ở cột 1: [2, 2, 1].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Liệt kê năm ô bị ảnh hưởng khi bấm dưới dạng độ lệch so với ô được bấm.
Gợi ý 2
Bỏ qua những độ lệch đưa ra ngoài bảng.
Gợi ý 3
Khi đếm, chỉ cần mỗi lần duyệt lại các ô cần xét là đủ.
Độ phức tạp mong đợi
thời gian O(q × rows × cols), bộ nhớ phụ O(rows × cols)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.