内存:128  时间:1

题目描述

暑假就要开始啦!小伙伴们又可以肆无忌惮的开黑吃鸡了喵!我们知道开黑吃鸡最重要的当然是团队合作了。在一个地图中,一个小队的玩家之间的距离不能太远,这样当队友遇到危险被击倒时才能保证有队友可以在足够的时间内赶过去。现在,我们有一个N*N的地图,其中“#”表示无法跨越的障碍物,其余符号均可通过,大写字母“A”-“Z”表示小队编号,队员在每个单位时间内只能上下左右移动一格(每个小队最多有4个人)。在一个小队中,如果当其中有一人被击倒,有至少一个队友可以在规定时间T内赶过去,那么我们认为这个小队是一个配合出色的小队。问题来了:在给定的地图中,有多少小队是配合出色的呢?(规定一个人的小队不是配合出色的)

输入

第1行,整数N(1≤N≤30),整数T(1≤T≤10)
第2~N+1行 输入N*N的地图。

输出

输出配合出色小队个数

样例输入

8 3
……..
….A…
……B.
……..
..B..B..
……..
..C…C.
……..

样例输出

1

提示

在样例中,共有A、B、C三个队伍,其中只有B小队的每个队员可以在三个单位时间内得到队友的救援。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
char mp[MAXN][MAXN];
int vis[MAXN][MAXN];
int num[30];
int flag[30];
int dis[4][2]={ {1,0},{0,1},{-1,0},{0,-1} };
struct node
{
    int x,y;
    int temp;
};
int main()
{
    int n,K;
    cin>>n>>K;
    memset(num,0,sizeof(num));
    memset(flag,0,sizeof(flag));
    memset(vis,0,sizeof(vis));
    for(int i=0; i<n; ++i)
        scanf("%s",mp[i]);
   // cout<<endl<<endl;
   // for(int i=0; i<n; ++i)printf("%s
",mp[i]);
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
        {
            if(mp[i][j]<='Z'&&mp[i][j]>='A')
            {
                num[mp[i][j]-'A']++;
            }
        }
    //for(int i=0; i<27; ++i)
        //if(num[i]>1)flag[i]=1;
    queue<node> que;
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
        {
            if(mp[i][j]<='Z'&&mp[i][j]>='A' && num[mp[i][j]-'A']>1)
            {
                memset(vis,0,sizeof(vis));
                while(!que.empty())que.pop();
                node p;
                p.x=i;p.y=j;p.temp=0;
                vis[i][j]=1;
                que.push(p);

                int fid=0;
                while(!que.empty())
                {
                    node hp=que.front();
                    que.pop();
                    if(hp.temp>=K)break;
                   // if()
                    for(int k=0; k<4; ++k)
                    {
                        int xx=hp.x+dis[k][0];
                        int yy=hp.y+dis[k][1];
                        if(xx>=0 && xx<=n && yy>=0 && yy<=n && mp[xx][yy]!='#' &&vis[xx][yy]==0)
                        {
                            vis[xx][yy]=1;
                            node qw;
                            qw.x=xx;
                            qw.y=yy;
                            qw.temp=hp.temp+1;
                            que.push(qw);
                            if(mp[xx][yy]==mp[p.x][p.y])fid=1;
                        }
                    }
                }
                if(fid==0)num[mp[i][j]-'A']=0;
            }
        }
    int c=0;
    for(int i=0; i<27; ++i)
        {
            if(num[i]>1){
                    c++;
            char tt='A'+i;
         //   cout<<tt<<endl;}
        }}
        cout<<c<<endl;
    return 0;
}
/*
30 10
...A....A.....................
....................#B........
.....A..............#.........
....................#.........
......C.............#.E.......
....................#.........
....................#.........
...................B#.........
....................#.........
......E...#.....E...#.........
###################...........
#D......D.#Z..................
###########.#########.........
.........D#D#E................
..............................
........Z...K.................
...........GIJ................
...........KJK................
...........LKL................
.....M................M.......
......################........
......#..H...##.H....#........
.....H#H.....##..F...#........
......#..##########..#........
......#.....####F....#........
......#...##.##.##...#........
......#.##...##...##.#........
......################........
.....M................M.......
..............................
*/

代码来源于互联网,仅供参考!