大家好，我是大四在校生，现在刚转到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

思路决定解题~！

ifinver 发表于 2014-9-15 11:23
完善一下资料应该就够了把-。-

恩恩  可以了现在

我也是新人哦

敏敏好学 发表于 2014-9-15 11:05
我也是新人，可是为什么我就没有权限发帖那....呜呜

完善一下资料应该就够了把-。-

不系之舟王 发表于 2014-9-15 11:18
同道中人啊！我也大四，不过技术好菜啊，加油啊！

加油加油~

同道中人啊！我也大四，不过技术好菜啊，加油啊！

我也是新人，可是为什么我就没有权限发帖那....呜呜

应该是char[]的效率是最高的

学习中。。一起加油

fantacyleo 发表于 2014-9-14 12:46
我倒没想DFS或BFS那么多，直接穷举了。二维数组，假定每一个点是十字架的中心点，判断其周围符号布局是否 ...

嗯嗯 ，正解，算法果然是不分编程语言的，哈哈

这题略叼，容我三思

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应该没问题

嗯，一起加油入学黑马吧！

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就能做出来。。你这个题有思路吗?

你不是用其他语言实现过了吗？选二维数组还是字符串这种问题，跟是否用Java无关嘛。另外可否告知：
1. 用时、内存限制
2. N的范围
3. 每个十字架仅由4个#号组成是什么意思？十字架正中那个可以是O而非#？

zxd6587 发表于 2014-9-13 16:43
一直在看啊！！好多了！

好吧 我才刚开始。。哈哈，一起加油吧~
我贴的这个题目你有思路不~

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

一直在看啊！！好多了！

zxd6587 发表于 2014-9-13 16:35
好牛的样子!我也大四！也想去黑马学习啊1

求交流求脸熟:loveliness:
你在看视频了吗

好牛的样子!我也大四！也想去黑马学习啊1