> 
> PKU 3338的另类过法
> 本题可能有多种解法，我的解法是一种很简单的模拟+DFS过的。本题是一次一次进行矩形切割
> 这样就可以当切下一块时，将整块编一个号。
> 譬如题的第一个SIMPLe：
> 3 5
> 3
> 1 1 3 2
> 4 0 2 3
> 4 0 5 1
> 开始初始化所有的编号为0，
> 当切下1 1 3 2这一块时，就将其编为1，这样就可以将所有的快都编好块，但是这里有一个问题，就是有重合的时候，怎么办？
> 这样就可以用本块以前的区域号+当前的区域号，就可以得到一个新的区域号，这样就可以区分每一次切割
> 如SIMPLe
> 1 1 3 2
> 开始全部初始化为0,count=1
> (1,1)->(3-1,2-1)都为0+count=1
> (2,0)->(4-1,3-1)都为2,但是由于(2,1)以前的编号为1,所以(2,1)的编号就为2+1=3
> 这样全部编完号后，DFS一遍就搞定了
> 最后的结果：
> 5712151	runformydream	3338	Accepted	564K	0MS	G++	1931B	2009-08-21 10:02:03

这个算法怎么证明是正确的？

3 4
4
2 3 4 1
2 1 3 0
2 2 4 1
1 3 2 0

应该是6吧 这个算法得出来是5

• Re:增加水题ac人数。。。 (141) gdczcpy 2010-07-11 20:04:10