2801 LOL-盖伦的蹲草计划
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题目描述 Description
众所周知，LOL这款伟大的游戏，有个叫盖伦的英雄。他的伟大之处在于他特别喜欢蹲草丛阴人（XL：蹲草阴人也算英雄？！CZQ：没办法，个个都是这么玩的）。某日，德玛西亚与诺克萨斯之间又发生了一场战斗，嘉文四世希望盖伦能带领一支K人的德玛西亚军队出战。
战斗发生在召唤师峡谷。整个召唤师峡谷被分割成M行N列的一个矩阵，矩阵中有空地和几片草丛。这几片草丛中有些很大、有些很小。一个1×1的草丛能容纳3个士兵，盖伦坚信蹲草偷袭战术能战胜诺克萨斯军队，所以他希望他的军队能全部蹲进草丛里。当然，为了不影响盖伦的作战，盖伦需要单独霸占连起来的一片草丛（不管草丛有多大）。
输入描述 Input Description
第一行M、N、K，表示矩阵的行数、列数和士兵数量。
接下来M行，输入矩阵，'.'代表平地，'*'代表草丛。
输出描述 Output Description
如果德玛西亚军队和盖伦都能躲进草丛里，则输出“Demacia Win!”，否则输出“Demacia Lose!”
样例输入 Sample Input
3 3 6
.**
...
.*.
样例输出 Sample Output
Demacia Win!
数据范围及提示 Data Size & Hint
1<=m、n<=1500
1<=k<=1500
P.S：这里对于两个1×1的草丛是否连在一起的定义是：对于每个1×1的草从，它与周围（上下左右）的草丛是连在一起的。
分类标签
思路：dfs+剪枝，不然会爆栈；
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define max(a,b) a>b?a:b;
int n,m,k,tem,dir[][]={{,},{-,},{,},{,-}};
char a[][];
long long int cnt,an;
void dfs(int si,int sj)
{
a[si][sj]='*';
int xx,yy;
for(int i=;i<;i++)
{
xx=si+dir[i][];
yy=sj+dir[i][];
if(xx>=&&xx<m&&yy>=&&yy<n&&a[xx][yy]=='.')
{
cnt++;
if(*cnt>=k)
return;
dfs(xx,yy); }
else
continue;
}
return ;
}
int main()
{
scanf("%d%d%d",&m,&n,&k);
int i,j;
for(i=;i<m;i++)
{
scanf("%s",a[i]);
}
for(i=;i<m;i++)
{
for(j=;j<n;j++)
{
if(a[i][j]=='.')
{
cnt=;
dfs(i,j);
an=max(cnt,an);
}
if(*an>=k)
break;
}
if(*an>=k)
break;
}
if(*an>=k)
printf("Demacia Win!\n");
else
printf("Demacia Lose!\n"); return ;
}