{"code":"24_hsg12_hanoi_khudancu","name":"Khu dân cư","description":"*Nguồn: Học sinh Giỏi THPT Hà Nội năm 2023 - 2024*\r\n\r\nBản đồ thành phố X có dạng lưới ô vuông $M$ hàng $N$ cột, các hàng được đánh số từ $1$ tới $M$, các cột được đánh số từ $1$ tới $N$. Mỗi ô vuông trên bản đồ có thể là **khu đất trống** hoặc **một khu dân cư** hoặc **một siêu thị**.   \r\n\r\nMỗi siêu thị chỉ có thể phục vụ các khu dân cư có khoảng cách so với nó không quá $D$, nghĩa là nếu siêu thị nằm ở ô $(x, y)$ thì nó có thể phục vụ được tất cả các khu dân cư nằm trong hình vuông có ô trái trên là $(x - D, y - D)$, ô phải dưới là $(x + D, y + D)$ (như *Hình 1*).\r\n\r\n![](https://cdn.algomaster.edu.vn/media/pagedown-uploads/d2d94bb2-2adb-433a-a957-84f84bcc8a28/image.png)\r\n\r\nMột khu dân cư gọi là \"chất lượng cao\" nếu được ít nhất $K$ siêu thị có thể phục vụ nó. Cho biết bản đồ của thành phố X, hãy đếm số lượng khu dân cư \"chất lượng cao\".\r\n\r\n#### Input\r\n\r\n*Dữ liệu vào từ tệp văn bản `KHUDANCU.INP`:*\r\n- Dòng đầu chứa bốn số nguyên $M, N, D$ và $K$ $(1\\le D \\le \\max(M, N); \\ 1\\le K\\le M \\times N)$; \r\n- $M$ dòng tiếp theo, mỗi dòng gồm $N$ ký tự, mỗi ký tự biểu diễn một ô vuông bản đồ. Mỗi ký tự sẽ thuộc một trong ba loại sau:\r\n    - `.` biểu diễn một khu đất trống;\r\n    - `P` biểu diễn một khu dân cư;\r\n    - `M` biểu diễn một siêu thị;\r\n\r\n- Dữ liệu đảm bảo tồn tại ít nhất một khu dân cư và ít nhất một siêu thị.\r\n\r\n#### Output\r\n\r\n*Kết quả ra tệp văn bản `KHUDANCU.OUT`:*\r\n- Ghi ra một số duy nhất là số khu dân cư \"chất lượng cao\".\r\n\r\n#### Examples\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5 5 1 2\r\n        P....\r\n        ....P\r\n        ..PM.\r\n        .M...\r\n        .....\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1\r\n        ```\r\n\r\n#### Note\r\n\r\n- Bản đồ minh hoạ thành phố $X$ như *Hình 2*.\r\n![](https://cdn.algomaster.edu.vn/media/pagedown-uploads/de0589ad-2c2d-49f7-963c-bcbacb9109e1/image.png)\r\n- Khu dân cư ở ô $(1, 1)$ không được siêu thị nào phục vụ;\r\n- Khu dân cư ở ô $(2, 5)$ được một siêu thị có thể phục vụ;\r\n- Khu dân cư ở ô $(3, 3)$ được hai siêu thị có thể phục vụ;\r\n- Vậy có một khu dân cư \"chất lượng cao\".\r\n\r\n#### Constraint\r\n\r\n- Có $40\\%$ số test ứng với $40\\%$ số điểm của bài thoả mãn: $M = 1; \\ N, D \\le 10^3$;\r\n- $20\\%$ số test khác ứng với $20\\%$ số điểm của bài thoả mãn: $M = 1; \\ N \\le 10^5$;\r\n- $20\\%$ số test khác ứng với $20\\%$ số điểm của bài thoả mãn: $2 \\le M, N \\le 1000;$ số khu dân cư, số siêu thị không vượt quá $1000$;\r\n- $20\\%$ số test còn lại ứng với $20\\%$ số điểm của bài thoả mãn: $2 \\le M, N \\le 1000$.","points":100.0,"partial":false,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}