吃鸡之团队合作
时间： 1ms 内存：128M
描述：
暑假就要开始啦！小伙伴们又可以肆无忌惮的开黑吃鸡了喵！我们知道开黑吃鸡最重要的当然是团队合作了。在一个地图中，一个小队的玩家之间的距离不能太远，这样当队友遇到危险被击倒时才能保证有队友可以在足够的时间内赶过去。现在，我们有一个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提示：
参考答案（内存最优[1124]）：
#include<stdio.h>
char a[30][30];
int b[30][30];
int s[26];
int num[26];
int sum=0;
int ans=0;
int n,t;
int flag=0;
int dx[4]={0,-1,0,1};
int dy[4]={1,0,-1,0};
int dfs(int x,int y,char c,int numbers)
{
if(numbers<=0)
return ;
int i;
for(i=0;i<4;i++)
{
int cx,cy;
cx=x+dx[i];
cy=y+dy[i];
if(cx>=0&&cx<n&&cy>=0&&cy<n&&b[cx][cy]==0&&a[cx][cy]!='#')
{
if(a[cx][cy]==c)
{
flag=1;
return ;
}
b[cx][cy]=1;
dfs(cx,cy,c,numbers-1);
b[cx][cy]=0;
}
}
}
int main()
{
scanf("%d %d",&n,&t);
int i,j;
for(i=0;i<n;i++)
{
scanf("%s",&a[i]);
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(a[i][j]>='A'&&a[i][j]<='Z')
{
if(s[a[i][j]-'A']==0)
{
s[a[i][j]-'A']=1;
ans++;
}
b[i][j]=1;
dfs(i,j,a[i][j],t);
b[i][j]=0;
if(flag==0)
{
if(num[a[i][j]-'A']==0)
{
num[a[i][j]-'A']=1;
sum++;
}
}
else
flag=0;
}
}
printf("%d",ans-sum);
return 0;
}
参考答案（时间最优[0]）：
#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\n",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.......
..............................
*/
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。