#include <iostream>
#include <cmath>
using namespace std;
int d[4][2] = {-1 , 0 , 1 , 0 , 0 , -1 , 0 , 1};
int mark[505][505];
char a[505][505];
int ans = 0;
int n , m , k;
inline void dfs(int x , int y){
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= m ; j++){
            int dx = i; 
            int dy = j;
            if(dx >= 1 && dx <= n && dy >= 1 && dy <= m && a[dx][dy] == '*' && mark[dx][dy] == 0 && abs(dx - x) + abs(dy - y) == k){
                mark[dx][dy] = 1;
                dfs(dx , dy);
            }
        }  
    }
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n >> m >> k;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= m ; j++){
            cin >> a[i][j];
            if(a[i][j] == '.') mark[i][j] = 1;
        }
    }
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= m ; j++){
            if(a[i][j] == '*' && mark[i][j] == 0){
                mark[i][j] = 1;
                dfs(i , j);
                ans++;
            }
        }   
    }
    cout << ans;    
    return 0;
}

【2阶-14】曼哈顿通讯站

题目描述

奇怪王国在自己 $n \times m$ 个区域的领土内建立了一些曼哈顿通讯站——当两个通讯站的曼哈顿距离刚好为 $d$ 时，这两个通讯站可以互相通讯。

现在王国 Karl 想知道，奇怪王国到底有多少个独立的通讯网络？

输入格式

第一行三个正整数 $n,m,d$。

接下来 $n$ 行每行 $m$ 个字符，依次表示对应网格的情况，* 表示网格上有通讯站，. 表示网格上无通讯站。

输出格式

一个整数表示结果。

样例 #1

样例输入 #1

3 4 2
**..
..**
*..*

样例输出 #1

3

样例 #2

样例输入 #2

5 5 4
*...*
.*.*.
.....
.*.*.
*...*

样例输出 #2

1

提示

• 对于 $50\%$ 数据：$5 \leq n,m \leq 10$，$1 \leq d \leq 5$。
• 对于 $100\%$ 数据：$100 \leq n,m \leq 500$，$1 \leq d \leq 100$。

晚点来看