1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

const int N = 1001;
const int M = 0; 
int n,m,d;
bool check(int x,int y)
{
    return x>=1&&x<=n&&y>=1&&y<=m;
}
bool wet[N][N];
char mp[N][N];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
queue<pair<int,pii>> q;
void init(int x,int y,int step)
{
    wet[x][y] = true;
    q.push({step,{x,y}});
}
void bfs()
{
    while(!q.empty())
    {
        int last = q.front().first;
        int curx = q.front().second.first;
        int cury = q.front().second.second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int nx = curx + dx[i];
            int ny = cury + dy[i];
            if(check(nx,ny)&&mp[nx][ny]!='#'&&!wet[nx][ny]&&last>=1)
            {
                wet[nx][ny] = true;
                q.push({last-1,{nx,ny}});
            }
        }
    }
}
void solve()
{
    cin >> n >> m >> d;
    for(int i=1;i<=n;i++)
    {
        cin.ignore();
        for(int j=1;j<=m;j++)
        {
            cin >> mp[i][j];
            if(mp[i][j]=='H')
            {
                init(i,j,d);
            }
        }
    }
    bfs();
    int cnt = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(wet[i][j]) cnt++;
        }
    }
    cout << cnt << endl;
}