Untitled

Lưới axit
Một lưới hình chữ nhật có kích thước N x M. Mỗi ô được làm bằng kim loại đặc biệt (loại A) hoặc làm bằng đá (loại B). 
Nếu axit được đổ lên một ô lưới, nó có thể làm tan chảy nó (đối với loại A: ô kim loại đặc biệt) và lan rộng hơn hoặc không đi qua nó (đối với loại B: ô đá).
Tế bào được làm bằng kim loại đặc biệt (loại A) có thể tan chảy với axit trong 1 giây và do đó cho phép axit lan rộng hơn.
Tế bào được làm bằng đá (loại B) không phản ứng với axit và do đó không tan chảy cũng như không cho axit đi qua nó.
 
Có loại ô thứ ba trống (loại C), nhưng có ranh giới (cả 4 mặt) được bọc bằng kim loại bảo vệ.
 
 


Hình. Ví dụ về lưới có kích thước 7 x 8 
 
Nếu cả 4 mặt của nó (loại C: ô trống) tiếp xúc với axit tại bất kỳ thời điểm nào, thì trong trường hợp đó ranh giới của nó (cả 4 mặt) sẽ tan chảy và cho phép axit đi qua nó. Trong trường hợp đó, nó (loại C: ô trống) chứa đầy axit. 
Chỉ có một và chỉ một ô như vậy trong một lưới nhất định.
 
Axit được đổ lên một trong các ô của lưới, ô này được làm bằng kim loại đặc biệt có thể tan chảy với axit.
Đảm bảo rằng axit sẽ chỉ được đổ vào một ô được làm bằng kim loại đặc biệt (loại A), không đổ lên đá (loại B) hoặc ô trống (loại C).
Axit được đổ liên tục cho đến khi tất cả các ô lưới (trừ đá loại B) tan chảy hoàn toàn.
 
Bạn phải biết khi nào ô trống có ranh giới bảo vệ đặc biệt sẽ bị đổ đầy axit và khi nào toàn bộ lưới sẽ bị đổ đầy axit (ngoại trừ các ô được tạo thành từ đá).
 
Phải mất 1 giây để axit hòa tan tế bào kim loại đặc biệt và sau đó nó có thể lan sang 4 cạnh trực giao của nó (Trái, Phải, Lên, Xuống).
 
Đầu vào:
 
Mục đầu tiên là số lượng ca kiểm thử; phần còn lại là đầu vào của mỗi trường hợp thử nghiệm.
Đối với mỗi trường hợp thử nghiệm, hàng đầu tiên chứa N và M là hai số nguyên cách nhau bởi dấu cách.
Hàng tiếp theo chứa vị trí ô (số hàng và số cột cách nhau bởi dấu cách) nơi axit sẽ được đổ liên tục cho đến khi toàn bộ lưới (trừ ô đá) tan chảy.
N hàng tiếp theo chứa M giá trị số nguyên, mỗi hàng chứa loại ô.
 
Giá trị loại ô có 3 loại:
    - 0 : ô là đá (loại B) 
    - 1: Cell được làm bằng kim loại đặc biệt (loại A)   
    - 2: ô là ô trống đặc biệt, có ranh giới đặc biệt (loại C)   
  Lưu ý: Luôn có một và chỉ một ô loại C (giá trị 2) trong một lưới nhất định. 
 
Đầu ra:
 
Đầu ra phải chứa 2 dòng cho mỗi trường hợp thử nghiệm.
Dòng đầu tiên: Số trường hợp  
Dòng thứ 2: Đếm1 Đếm2    
    Ở đâu:
            Count1: thời gian tính bằng giây khi ô trống đặc biệt (loại C) sẽ được lấp đầy. 
            Đếm2: thời gian tính bằng giây khi toàn bộ lưới sẽ chứa đầy nước (lưu ý: ô đá không thể chứa đầy axit).   
 
Ghi chú:
1. Count2 sẽ là -1 nếu tất cả các ô của lưới (trừ ô đá) không thể hòa tan được. Thuật ngữ hòa tan toàn bộ lưới có nghĩa là tất cả các ô ngoại trừ đá đều chứa đầy Axit.   
2. Count1 sẽ là -1 nếu không thể lấp đầy ô trống. Nếu không thể điền vào ô trống thì số 1 cũng được áp dụng, tức là Count2 = -1. 
3. Khi axit đi vào tế bào đặc biệt, nó sẽ tích tụ ở đó trong 1 giây. Sau đó axit bắt đầu rò rỉ sang các tế bào lân cận (trái, phải, trên, dưới).   
4. Các thuật ngữ “hòa tan”, “tan chảy”, “rò rỉ” được dùng để diễn đạt ý nghĩa tương tự việc tế bào bắt đầu rò rỉ axit sang các tế bào lân cận (trái, phải, trên, dưới). 
5. Axit được đổ liên tục nên khi một tế bào bắt đầu rò rỉ axit, nó có thể lan rộng hơn sang các tế bào khác trong thời gian dài hơn.
6. Số lượng hàng hoặc cột tối đa của lưới là 3000. 
 
Đầu vào mẫu:
9 ---->Số lượng test.      
4 5 -------> N=4: số hàng, M= 5: số cột      
2 4 ------> Vị trí ô (hàng col) nơi đổ axit          
1 0 1 0 1 ------> Lưới hàng đầu tiên với các mục nhập ô M    
1 0 1 1 1 ----> Đổ axit vào ô thứ 4 của hàng ( thứ 2 ) này.      
1 1 2 1 1 -----> Hàng chứa ô trống (loại C: value: 2)     
1 0 1 0 1 -------> Hàng cuối cùng của lưới có giá trị ô M        
3 3 ------> Bắt đầu trường hợp thử nghiệm thứ 2, N=3, M=3   
1 2 ---> Vị trí đổ axit    
1 1 0 ---> hàng lưới thứ 1; Axit đổ vào ô thứ 2 của hàng (1 ) này của lưới.  
1 2 1
0 1 1
3 3
1 1
1 1 1
1 2 1
0 1 1
3 3
3 3
1 1 1
1 2 1
0 1 1
4 4
2 3
0 0 1 0
0 1 1 1
1 1 2 1
1 0 1 1
3 3
1 3
0 1 1
1 2 1
1 1 1
4 5
1 3
1 0 1 0 1
1 0 1 1 1
1 1 1 2 1
1 0 0 1 1
4 5
3 5
1 0 1 0 1
1 0 1 1 1
1 1 1 2 1
1 0 0 1 1
4 5
2 4
1 0 1 0 1
1 1 1 1 1
1 1 2 1 1
1 0 1 1 1
 
Đầu ra mẫu:
Trường hợp 1
-1 -1 --->Count1 Count2 (tham khảo mô tả đầu ra)              
Trường hợp số 2
-1 -1
Trường hợp số 3
6 6
Trường hợp số 4
6 6
Trường hợp số 5
5 5
Trường hợp số 6
6 6
Trường hợp số 7
7 7
Trường hợp số 8
5 9
Trường hợp số 9
4 6