A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

    大家好,我是大四在校生,现在刚转到java,并下定决心来黑马学习,求和同学们混个脸熟啊~。我在大一大二的时候学过一段时间的java,所以现在学起来挺容易接受的,java和C++、C#又是大同小异,嘿嘿。
  感觉技术分好难赚啊,求同学们指教指教~谢谢。
  第一篇帖子就发算法题吧,是个ACM算法竞赛比赛题,中等难度,现在换用java实现,感觉好难啊:'(,半天写不出来。。
  下面上题目,求同学们分享一下解题思路啊,然后一起写代码实现,如何~
我感觉都会加分的哦。回帖奖励黑马币,come on~

  题目是这样的:
  输入一个字符矩阵,每个位置的字符要么是'o'要么是'#',输出所给矩阵的由'#'组成的十字架的数量。
  比如下图figure1中有1个十字架


要求:
1、每个十字架仅由4个#号组成。
2、每个十字架必须是独立的,如上图figure2中,第四行第三个字符是#,和上面的十字架连在了一起,就不算。
3、上图2、3、4十字架数量为0
输入规则:
1、输入包含多组测试用例
2、每组测试用例中,先输入一个数字N,表示矩阵是N*N的。
3、输入0时结束
输出规则:
对于每组测试数据,输出一个整数N,表示矩阵中有N个十字架。
样例输入:
4oo#o          o###oo#oooo#4oo#o          o###oo#ooo#o5oo#oooo#oo          #####oo#oooo##o6ooo#ooooo##o          o#####ooo#ooooo#oooooooo0
样例输出:
1000


题目就这样,求同学给个解题思路啊。还有用什么存储矩阵好呢,用二维char数组好些还是一维String?还是StringBuffer?


原题在杭电的OnlineJudge上(当前正在比赛,练习系统关掉了,晚一小会就开了):http://acm.hdu.edu.cn/showproblem.php?pid=4414

评分

参与人数 2技术分 +2 收起 理由
杨佳名 + 1 赞一个!
付江涛 + 1 赞一个!

查看全部评分

19 个回复

倒序浏览
好牛的样子!我也大四!也想去黑马学习啊1
回复 使用道具 举报
zxd6587 发表于 2014-9-13 16:35
好牛的样子!我也大四!也想去黑马学习啊1

求交流求脸熟:loveliness:
你在看视频了吗
回复 使用道具 举报

回帖奖励 +1

ifinver 发表于 2014-9-13 16:37
求交流求脸熟
你在看视频了吗

一直在看啊!!好多了!
回复 使用道具 举报
zxd6587 发表于 2014-9-13 16:43
一直在看啊!!好多了!

好吧 我才刚开始。。哈哈,一起加油吧~
我贴的这个题目你有思路不~
回复 使用道具 举报
你不是用其他语言实现过了吗?选二维数组还是字符串这种问题,跟是否用Java无关嘛。另外可否告知:
1. 用时、内存限制
2. N的范围
3. 每个十字架仅由4个#号组成是什么意思?十字架正中那个可以是O而非#?
回复 使用道具 举报
fantacyleo 发表于 2014-9-13 16:49
你不是用其他语言实现过了吗?选二维数组还是字符串这种问题,跟是否用Java无关嘛。另外可否告知:
1. 用时 ...

嗯 我用C++实现过 在这http://www.cnblogs.com/ifinver/archive/2012/09/28/2706469.html
1、因为我是想用这个题目练习一下java,就没加内存和时间的限制-。-
2、题目的要求是N行N列的矩阵,其中3<=N<=50
3、我错了。。。是5个#。。中间必须是#。。谢哥哥指正。


我当时用C++测试过,用二维字符数组是最高效的。但是java这种托管机制不知道最高效的是什么,按道理应该也是二维char数组把?

我是外循环线性遍历,内层套个深搜匹配做出来的,感觉效率不高,我看有人直接BFS就能做出来。。你这个题有思路吗?

回复 使用道具 举报
星海 初级黑马 2014-9-14 12:11:36
8#

回帖奖励 +1

嗯,一起加油入学黑马吧!
回复 使用道具 举报

回帖奖励 +1

ifinver 发表于 2014-9-14 11:33
嗯 我用C++实现过 在这http://www.cnblogs.com/ifinver/archive/2012/09/28/2706469.html
1、因为我是想 ...

我倒没想DFS或BFS那么多,直接穷举了。二维数组,假定每一个点是十字架的中心点,判断其周围符号布局是否满足题意。根据这个思路,十字架中心点只可能出现在内圈(N-2)^2个点中。判定十字架的复杂度是O(1),因此整个算法是O((N-2)^2),应付N<=50应该没问题
回复 使用道具 举报

回帖奖励 +1

这题略叼,容我三思
回复 使用道具 举报
fantacyleo 发表于 2014-9-14 12:46
我倒没想DFS或BFS那么多,直接穷举了。二维数组,假定每一个点是十字架的中心点,判断其周围符号布局是否 ...

嗯嗯 ,正解,算法果然是不分编程语言的,哈哈
回复 使用道具 举报

回帖奖励 +1

学习中。。一起加油
回复 使用道具 举报
应该是char[]的效率是最高的
回复 使用道具 举报
我也是新人,可是为什么我就没有权限发帖那....呜呜
回复 使用道具 举报
不系之舟王 来自手机 中级黑马 2014-9-15 11:18:02
15#
同道中人啊!我也大四,不过技术好菜啊,加油啊!
回复 使用道具 举报
不系之舟王 发表于 2014-9-15 11:18
同道中人啊!我也大四,不过技术好菜啊,加油啊!

加油加油~
回复 使用道具 举报
敏敏好学 发表于 2014-9-15 11:05
我也是新人,可是为什么我就没有权限发帖那....呜呜

完善一下资料应该就够了把-。-
回复 使用道具 举报
我也是新人哦
回复 使用道具 举报
ifinver 发表于 2014-9-15 11:23
完善一下资料应该就够了把-。-

恩恩  可以了现在
回复 使用道具 举报
思路决定解题~!
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马