Description

2019-ncov的突然出现扰乱了人们的日常生活，它具有极强的传染性，可以快速的在人群中扩散，现在研究人员正在模拟其在人群中的扩散情况.

在一个n*m矩阵所示的人群中，*为普通人，#为佩戴口罩的人，@为病毒携带者，已知每秒每位病毒携带者会将病毒传染给相邻八个方向的未戴口罩的普通人。请问 x 秒后会有多少名传染者（初始为第0秒）？

Input

第一行输入空格分隔的三个数n，m，x代表n行，m列的空间，x秒（n,m<=1000)。

接下来n行每行m人如上述所示。

Output

一个数字，代表最终被传染的人数。

Sample

Input
4 4 2

****
*@**
**##
**#*

Output
12

#include <iostream>
#include <bits/stdc++.h>
#define Max 0x3f3f3f3f
using namespace std;

struct node
{
    int x,y;
    int minute;
};

int X[] = {0,0,-1,1,1,1,-1,-1};
int Y[] = {1,-1,0,0,1,-1,1,-1};
char Map[1005][1005];
bool vis[1005][1005];
int minutes[1005][1005];
int n,m,T,cnt;
//cnt 记录总数

void BFS(node start)
{
    node now,next;
    minutes[start.x][start.y] = 0;
    vis[start.x][start.y] = true;
    queue <node> q;
    q.push(start);
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        if(now.x<0 || now.x>=n || now.y<0 || now.y>=m)
            continue;
        for(int i=0;i<8;i++)
        {
            next.x = now.x+X[i];
            next.y = now.y+Y[i];
            next.minute = now.minute+1;
            if(Map[next.x][next.y]!='#' && !vis[next.x][next.y])
            {
                vis[next.x][next.y] = true;
                minutes[next.x][next.y] = min(next.minute,minutes[next.x][next.y]);
                q.push(next);
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);

    //初始化
    memset(minutes,Max,sizeof(minutes));
    memset(vis,false,sizeof(vis));
    cnt=0;
    node start;
    cin>>n>>m>>T;
    for(int i=0;i<n;i++)
        cin>>Map[i];
        
    //不一定就一个病毒携带者
    //可能多次BFS
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(Map[i][j] == '@')
            {
                start.x = i;
                start.y = j;
                start.minute = 1;
                BFS(start);
            }
        }
    //判断时间
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(minutes[i][j] <= T+1)
                cnt++;
        }
    cout<<cnt<<endl;
    return 0;
}