题目大意
给定一个2∗m2*m2∗m仅由字符WWW和BBB的矩阵,求是否有路径可以经过所有BBB而不经过任何WWW。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路
虽然很多人讲的都是数组dp,但是这个东西实际上会有些抽象和复杂。
其实不如直接模拟这个过程。用一个flag来存储当前位置在上方还是下方。
如下:
> 以下所有cb均表示'B',cw均表示'W'。
> a,b均为string,表示矩阵的两行,且处理以后从下标1开始。
> i初始化为1。
1
如果开头有多个上下两个B则不是很好处理。
注意到开头连续的上下两个B并不会影响到后续的位置在上方或下方,所以可以直接过滤掉:
2
首先确保当前停下来的列不是两个W:
然后如果当前已经到达了m+1(即整个矩阵都是B)那么可以直接输出答案后返回。
3
此时只剩当前列一个W一个B的情况了,需要根据具体情况确定flag初始值。
注意完成后要i++来到真正的处理位置。
4
for(;i <= m;i++)开始遍历。
首先,如果当前位置是'W',则代表没有办法继续往下走了。
然后,如果当前列两个位置都是B,则为了都遍历到需要换一行。
5
如果最后没有输出NO,则证明已经到达了,有一条正确路径,直接cout << "YES\n";即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码