Như đã biết, các Pharaoh là những người đầu tiên khám phá vũ trụ. Họ đã phóng con tàu vũ trụ đầu tiên lên hành tinh Thutmus I (ngày nay được biết đến với tên gọi Sao Hỏa). Bề mặt hành tinh có thể được mô hình hóa bằng một lưới gồm \((2n+1)\times(2n+1)\) ô vuông, mỗi ô chứa đất hoặc nước. Trạng thái của ô ở hàng \(i\), cột \(j\) (\(0\le i,j\le 2n\)) được ký hiệu bởi \(s[i][j]\): \(s[i][j]=\) '1' nếu ô chứa đất và \(s[i][j]=\) '0' nếu ô chứa nước.

Hai ô đất được gọi là liên thông nếu tồn tại một đường đi chỉ gồm các ô đất nối chúng, trong đó hai ô liên tiếp luôn có chung một cạnh. Một hòn đảo trên hành tinh là một tập tối đại các ô đất sao cho hai ô bất kỳ trong tập đều liên thông với nhau.

Nhiệm vụ của con tàu là đếm số hòn đảo trên hành tinh. Tuy nhiên, nhiệm vụ này không dễ dàng vì con tàu sử dụng một máy tính cổ đại. Máy tính có bộ nhớ \(h\), là một mảng hai chiều kích thước \((2n+1)\times(2n+1)\). Mỗi phần tử của mảng chứa được một xâu nhị phân độ dài \(100\), trong đó mỗi ký tự là '0' (ASCII 48) hoặc '1' (ASCII 49). Ban đầu, ký tự đầu tiên của mỗi ô nhớ lưu trạng thái của ô tương ứng trên lưới:

với mọi \(0\le i,j\le 2n\). Tất cả các ký tự còn lại của \(h\) ban đầu đều là '0' (ASCII 48).

Để xử lý dữ liệu trong bộ nhớ, máy tính chỉ có thể truy cập một vùng \(3\times3\) và ghi đè giá trị tại ô trên cùng bên trái của vùng đó. Cụ thể, máy tính có thể truy cập các giá trị \(h[i..i+2][j..j+2]\) (\(0\le i,j\le 2(n-1)\)) rồi ghi đè giá trị tại \(h[i][j]\). Thao tác này được gọi là xử lý ô \((i,j)\).

Để khắc phục giới hạn của máy tính, các Pharaoh sử dụng cơ chế sau:

• Máy tính xử lý bộ nhớ qua \(n\) bước.
• Ở bước \(k\) (\(0\le k\le n-1\)), đặt \(m=2(n-k-1)\). Máy tính xử lý ô \((i,j)\) với mọi \(0\le i,j\le m\), theo thứ tự tăng dần của \(i\), và với mỗi \(i\) theo thứ tự tăng dần của \(j\). Nói cách khác, thứ tự xử lý là \((0,0),(0,1),\ldots,(0,m),(1,0),(1,1),\ldots,(1,m),\ldots,(m,0),(m,1),\ldots,(m,m)\).
• Ở bước cuối cùng (\(k=n-1\)), máy tính chỉ xử lý ô \((0,0)\). Sau đó, giá trị ghi tại \(h[0][0]\) phải biểu diễn số hòn đảo trên hành tinh dưới dạng nhị phân, với bit có trọng số nhỏ nhất nằm ở ký tự đầu tiên của xâu.

Hình dưới đây minh họa cách máy tính xử lý một bộ nhớ kích thước \(5\times5\) (\(n=2\)). Ô màu xanh lam là ô đang bị ghi đè; các ô được tô màu tạo thành vùng đang được xử lý.

Trong bước \(0\), máy tính xử lý các vùng dưới đây theo thứ tự từ trái sang phải:

Trong bước \(1\), máy tính chỉ xử lý một vùng:

Hãy cài đặt một phương pháp cho phép máy tính đếm số hòn đảo trên hành tinh Thutmus I theo đúng cơ chế hoạt động trên.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau. Chữ ký C++ trong tệp tiêu đề chính thức là:

std::string process(std::vector<std::vector<std::string>> a,
                    int i, int j, int k, int n);

• a: mảng \(3\times3\) biểu diễn vùng đang được xử lý; cụ thể, \(a=h[i..i+2][j..j+2]\). Mỗi phần tử của a là một xâu có độ dài đúng bằng \(100\), và mỗi ký tự là '0' (ASCII 48) hoặc '1' (ASCII 49).
• i, j: lần lượt là chỉ số hàng và cột của ô máy tính đang xử lý.
• k: chỉ số của bước hiện tại.
• n: tổng số bước; bề mặt hành tinh có kích thước \((2n+1)\times(2n+1)\) ô.
• Hàm phải trả về một xâu nhị phân độ dài đúng bằng \(100\). Giá trị trả về sẽ được lưu vào ô nhớ \(h[i][j]\).
• Lần gọi cuối cùng xảy ra khi \(k=n-1\). Trong lần gọi này, hàm phải trả về biểu diễn nhị phân của số hòn đảo trên hành tinh: bit có trọng số nhỏ nhất ở vị trí \(0\) (ký tự đầu tiên), bit có trọng số nhỏ thứ hai ở vị trí \(1\), và cứ tiếp tục như vậy.
• Hàm này bắt buộc phải độc lập với mọi biến tĩnh hoặc biến toàn cục; giá trị trả về chỉ được phụ thuộc vào các tham số truyền vào.

Mỗi test chứa \(T\) kịch bản độc lập, tương ứng với các bề mặt hành tinh khác nhau. Hoạt động của lời giải cho mỗi kịch bản phải độc lập với thứ tự của các kịch bản, vì các lời gọi process thuộc cùng một kịch bản có thể không diễn ra liên tiếp nhau. Tuy nhiên, đối với từng kịch bản, các lời gọi process được bảo đảm xuất hiện theo đúng trình tự đã mô tả ở trên.

Ngoài ra, trong mỗi test, nhiều phiên bản chương trình của bạn có thể được khởi chạy đồng thời. Giới hạn thời gian và bộ nhớ được tính gộp cho tất cả các phiên bản này. Mọi hành vi cố ý truyền dữ liệu ngoài giao thức giữa các phiên bản chương trình đều bị coi là gian lận và có thể dẫn đến việc bị loại khỏi kỳ thi.

Đặc biệt, mọi thông tin lưu trong biến tĩnh hoặc biến toàn cục trong một lần gọi process không được bảo đảm còn tồn tại ở các lần gọi tiếp theo.

Ràng buộc

• \(1\le T\le10\).
• \(1\le n\le20\).
• \(s[i][j]\) là '0' (ASCII 48) hoặc '1' (ASCII 49), với mọi \(0\le i,j\le2n\).
• Độ dài của \(h[i][j]\) đúng bằng \(100\), với mọi \(0\le i,j\le2n\).
• Mỗi ký tự của \(h[i][j]\) là '0' (ASCII 48) hoặc '1' (ASCII 49), với mọi \(0\le i,j\le2n\).

Trong mỗi lần gọi process:

• \(0\le k\le n-1\).
• \(0\le i,j\le2(n-k-1)\).

Phân nhóm

1. (\(6\) điểm) \(n\le2\).
2. (\(8\) điểm) \(n\le4\).
3. (\(7\) điểm) \(n\le6\).
4. (\(8\) điểm) \(n\le8\).
5. (\(7\) điểm) \(n\le10\).
6. (\(8\) điểm) \(n\le12\).
7. (\(10\) điểm) \(n\le14\).
8. (\(24\) điểm) \(n\le16\).
9. (\(11\) điểm) \(n\le18\).
10. (\(11\) điểm) \(n\le20\).

Ví dụ

'1' '0' '0'
'1' '1' '0'
'0' '0' '1'

process([["100","000","000"],["100","100","000"],["000","000","100"]],0,0,0,1)

'1' '1' '0' '1' '1'
'1' '1' '0' '0' '0'
'1' '0' '1' '1' '1'
'0' '1' '0' '0' '0'
'0' '1' '1' '1' '1'

process([["100","100","000"],["100","100","000"],["100","000","100"]],0,0,0,2)
process([["100","000","100"],["100","000","000"],["000","100","100"]],0,1,0,2)
process([["000","100","100"],["000","000","000"],["100","100","100"]],0,2,0,2)
process([["100","100","000"],["100","000","100"],["000","100","000"]],1,0,0,2)
process([["100","000","000"],["000","100","100"],["100","000","000"]],1,1,0,2)
process([["000","000","000"],["100","100","100"],["000","000","000"]],1,2,0,2)
process([["100","000","100"],["000","100","000"],["000","100","100"]],2,0,0,2)
process([["000","100","100"],["100","000","000"],["100","100","100"]],2,1,0,2)
process([["100","100","100"],["000","000","000"],["100","100","100"]],2,2,0,2)

"011", "000", "000", "100", "100"
"111", "111", "011", "000", "000"
"110", "010", "111", "100", "100"
"000", "100", "000", "000", "000"
"000", "100", "100", "100", "100"

process([["011","000","000"],["111","111","011"],["110","010","111"]],0,0,1,2)

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau; đây chỉ là giao diện của trình chấm mẫu, không phải giao diện chuẩn vào/ra của bài:

• Dòng \(1\): \(T\).
• Khối \(i\) (\(0\le i\le T-1\)) mô tả kịch bản thứ \(i\):
  • Dòng \(1\) của khối: \(n\).
  • Dòng \(2+j\) (\(0\le j\le2n\)): \(s[j][0]\ s[j][1]\ \ldots\ s[j][2n]\).

Trình chấm mẫu in trên dòng \(1+i\) giá trị trả về cuối cùng của process cho kịch bản thứ \(i\) dưới dạng thập phân.

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2022, Ai Cập: gói nguồn chính thức của bài Mars.