你在哪?
时间限制(普通/Java):1000MS/5000MS 运行内存限制:65536KByte
总提交:304 测试通过:126
描述
春天来了，GG和MM去一个有N个景点的公园春游。在游玩过程中，他们觉得无聊，想起了小时候一起玩得捉迷藏游戏。不过和以往不同，这次是GG藏，MM总是从景点1开始找。聪明的MM能不能找到GG呢？
由于GG会耍赖（翻墙，钻洞……!@#$%），他可能会躲到一个MM怎么也找不到的景点里。
输入
本题有多组测试数据，每组测试数据由一下内容组成：
第一行为一个整数N，K（2<=N<=50, 1<=K<=N），表示有N个景点，GG躲在景点K。
以下为一个N×N的矩阵，表示任意两个景点是否相连。（1表示相连，0表示不相连）
输出
对每组测试数据输出一行。
如果MM能够找到GG，则输出“Clever MM!”，否则输出“Naughty GG!”。
样例输入
3 3
1 1 0
1 1 1
0 1 1
2 2
1 0
0 1
样例输出
Clever MM!
Naughty GG!
提示
BFS or DFS.
题目来源
xFengChenx、Narashy
分析 水题--深度优先
#include <iostream>
#include <stack>
#include <string.h>
int a[50*50],f[50];
using namespace std;
int main()
{
stack<int> sta;
int n,k,i,j,flag,_top;
while (scanf("%d%d",&n,&k)!=EOF)
{
flag=0;
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
scanf("%d",&a[i*n+j]);
}
}
memset(f,0,sizeof(f));
f[0]=1;
if (k!=1)
{
sta.push(0);
}
else
flag=1;
while (!sta.empty())
{
_top=sta.top();
sta.pop();
for(i=0;i<n;i++)
{
if (a[_top*n+i]==1&&f[i]==0)
{
sta.push(i);
f[i]=1;
if (i+1==k)
{
flag=1;
}
}
}
}
if (flag)
{
printf("Clever MM!\n");
}
else
printf("Naughty GG!\n");
}
return 0;
}