上善若水

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  2 Posts :: 32 Stories :: 2 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

最新随笔

搜索

  •  

积分与排名

  • 积分 - 10174
  • 排名 - 1166

最新评论

阅读排行榜

评论排行榜

你在哪?

时间限制(普通/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;
}

posted on 2009-11-23 08:12 上善若水 阅读(142) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理