代码之家 › 专栏 › 技术社区 › zeroDivisible

在解决这个与算法有关的问题时,我可以要求一些指导吗?

language-agnostic algorithm

zeroDivisible · 技术社区 · 15 年前

在空闲时间,我喜欢通过解决Topcoder.com或uva.onlinejudge.com等网页上的问题来提高我的算法/编程技能(好吧,我的技能太差了,我试图提高它们)。通常,我可以为更简单的问题编写和编写正确的算法——我了解有关递归或图形的大多数基本概念。

问题是,大多数时候,我无法解决更难的问题。至于现在,我偶然发现了这个(spoj.pl):

小约翰尼在玩他的小魔法邮票,试图画一张纸上的兔子方块字K乘K分为单位带边1的正方形。约翰尼的邮票是有边3的正方形,由边为1的小正方形。确切地其中两个正方形是突起的。而且,两个突起的正方形都是在同一行或同一列中。如果约翰尼想用这张邮票,他把它压成碎片以这样一种方式突起的正方形正好与一些相匹配方格纸。如果一些凸出的正方形碰到了那块纸上的触摸方块一张纸改变了它的颜色从黑到白或从白到黑色。小邮票可以印部分在纸的外面, 但是突起的正方形总是必须躺在里面。邮票可以是以任何方式移动,但不能旋转。

一开始这张纸是全白。兔子包括一些黑色的方块 (剩下的必须是白色)。约翰尼试图画兔子。带着他的小邮票很久了时间,但他没有成功并不一定意味着不能画兔子,但只能画画画很难在这么大的一张纸上用这么小的邮票!)所以他问他的哥哥,大约翰,寻求帮助。

大约翰可以帮助小约翰尼给他一张神奇的大邮票。这个大邮票的大小是S乘S,并有一个任意数量的突起方格(这些方格没有必须位于行或列相同)。这张邮票有效就像小邮票,但是实施一个附加约束它只能按在如果它完全位于一张纸

在大约翰给小约翰尼之前他的大印,他想做当然,一起使用的邮票足以吸引兔子。他问道。你需要帮助来决定。输入

标准输入的第一行包含一个整数t(1_t_10) 表示测试用例的数量。

单个测试用例的描述以两个整数的行开始和k(1_S_K_ 1000,1_S_ 200) 由单个空间分隔。他们表示大约翰邮票的大小以及那张纸的大小。

以下三行包含小约翰尼的描述邮票。每行包含三个字符0或1。这样的说明显示白色一张纸看起来像按下小图章:0表示一个白色的正方形,一个黑色的正方形。里面正好有两个字符这三行是一行两者位于同一行或在同一列中。请注意这种描述不能说明邮票本身的设计图章与绘制的图形对称在那张纸上。

以下s行包含大约翰邮票的描述类似的格式;这种描述但是,可以包含任意个数。以下k行用同样的格式描述兔子就像在描述邮票。一个代表黑色正方形,而0_ 正方形的

产量

对于每个测试用例,写出标准输出带单词“是”(不带引号) 或“否”,取决于可以从测试用例中提取兔子使用测试用例中的图章 (一起)

例子

对于输入数据:
2 
3 8
010
000 
010
000
010
011
01100000   
00100000   
00010000   
00001100   
00011110   
10111100  
01111100   
01111110  
5 10  
001   
001  
000 
00000  
10100 
00001
00001
00100
0011110000
0000111000
0010011100
0111001110
1110000000
1101001000
1000001100
0110110110
0001001000
0000110000
正确的输出是:
NO
YES

诀窍是,我可以编写简单的解决方案,但这并不意味着我可以编写困难的解决方案。与此类似的是,在某些游戏中,在达到一定水平后,杀死弱小的敌人不会给你任何(或非常低的)经验。

我不需要任何解决方案,也不需要现成的算法——但是我可以要求一些指导原则吗?

当试图解决这类问题(或这类具体问题)时,正确的思维方式是什么?

3 回复 | 直到 13 年前

djna 15 年前

解决问题的本质是,它结合了你目前掌握的知识和敏锐的洞察力。我认为没有一种“正确”的思维方式。相反,我建议你制定一系列应对问题的策略。例如(这些不一定适用于这个问题,但我观察自己在解决问题时做这些事情)

一定要弄明白问题所在,好好处理一下(事实上,我会这么说的是 “正确”的事情)
列出你所知道的,在列表中寻找模式
试着解决相反的问题,而不是证明什么可以做,而是确定什么不能做
用手解决一些问题,看看是否会出现一些常见的模式
解决一个简单的问题-分而治之

有意思的是,如果你“玩弄”这些问题,就会想到很多意想不到的想法,通常就在你之后。停止思考这个问题。

在这种情况下,我想知道,给了几个图章,你如何能确定一个像素,不能设置…嗯,这必须取决于白空间的模式…看,我们在考虑逆问题-我们不要画画。

Michael Riley - AKA Gunny 15 年前

我十二岁的时候在一个小组里上过魔术课。魔术师叫乔·卡罗塔。有一次他耍了个花招,我脱口而出,“你是怎么做到的?”他那天说的话一直困扰着我。

乔的回答是:“迈克尔,如果你真的想知道这个把戏是怎么完成的,你必须自己想办法。”

当然,这不是我想听到的,但它确实让我的注意力集中在解决问题上。从我的角度来看,不仅仅是解决问题,而是解决问题。如果我第一次尝试解决这个问题时采取了17个步骤,而且非常笨拙,那么好消息是我解决了这个问题。

然后,通过查看我开发的解决方案并寻找改进该解决方案的方法,我将学习如何简化最终结果。后来在我的计算机编程生涯中,我发现这个过程被称为“逐步改进”。

它起作用了,但现在仍然起作用。

Michael Schier 14 年前

我是这样解决的: 首先,我检查了小邮票中的两个黑色条目是在同一列中还是在同一列中。为了简化,我旋转了所有邮票,如果它们在同一行,也就是说,当它们在同一列时,我只需要考虑这种情况。

接下来,我只使用小邮票简化了给定的KXK图片。我尝试将黑色像素移离上下边框,并将它们合并到中间。然后,您应该以包含黑色像素的一行或两行结束,这取决于小图章上黑色像素之间的距离是一行还是两行。

接下来,我在大邮票上应用了相同的简化方法(用小邮票简化大邮票)。然后,您可以通过反复应用大图章,从左到右简化图片。在这些步骤之间,使用小图章确保不超过两行包含黑色像素。

最后,检查应该很容易…