Loại cờ mới (DUTPC'21)

Xem PDF



Tác giả:
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Hôm nay, Khôi và những người bạn, chơi 1 loại cờ mới. Bàn cờ có dạng 1 lưới hình vuông có kích thước n × m, được chia làm các ô hình vuông nhỏ kích thước \(1 * 1\). Mỗi ô vuông \((𝑖,𝑗)\) được mô tả trạng thái bởi ký tự \(𝑎_{𝑖,𝑗}\). Nếu \(𝑎_{𝑖,𝑗} =\)# thì ô vuông này đã bị chặn, nếu \(𝑎_{𝑖,𝑗} =\). thì ô vuông này còn trống, và nếu \(𝑎_{𝑖,𝑗} = x\) với \(x\) là 1 số nguyên thì ô vuông này chứa quân cờ của người chơi thứ \(x\).

Trò chơi được chơi theo lượt. Khi tới lượt, người chơi mở rộng lãnh địa bằng cách đặt cờ của mình vào các ô trống ở gần các quân cờ người đó đang sở hữu, với điều kiện là có thể dùng các bước đi lên, đi xuống, qua trái qua phải để đi tới các ô trống đó từ quân cờ gần nhất của người chơi mà không phải đi qua các ô bị chặn hoặc ô chứa cờ của người chơi khác, và số bước đi phải bé hơn \(s_i\) (với \(s_i\) là tốc độ mở rộng của người chơi thứ \(i\)). Người chơi xác định số ô có thể đặt cờ và đặt cờ vào cùng 1 lúc, và lượt sẽ được chuyển qua cho người tiếp theo. Trò chơi kết thúc sau khi không còn ai có thể đi được nữa.

Hãy đếm xem mỗi người chơi sẽ có bao nhiêu quân cờ trên bàn sau khi trò chơi kết thúc.

Input

  • Dòng đầu tiên có 3 số nguyên \(n, m, p (1 ≤ 𝑛, 𝑚 ≤ 1000, 1 ≤ 𝑝 ≤ 9)\) – kích thước của bàn cờ và số lượng người chơi.
  • Dòng thứ 2 có \(p\) số nguyên \(s_i (1 ≤ 𝑠_𝑖 ≤ 10^9)\) - tốc độ mở rộng của từng người chơi.
  • \(n\) dòng tiếp theo, dòng thứ i chứa \(m\) kí tự \(𝑎_{𝑖,1}, 𝑎_{𝑖,2}, … , 𝑎_{𝑖,m}\)
  • Dữ liệu luôn đảm bảo mỗi người chơi đều có ít nhất 1 quân cờ của mình trên bàn cờ.

Output

  • In ra \(p\) số nguyên các nhau bởi dấu cách – số quân cờ của từng người chơi trên bàn khi trò chơi kết thúc

Example

Test 1

Input
3 3 2
1 1
1..
...
..2
Output
6 3

Bình luận