题目是酱滴，你是一个吃豆人，输入下面的参数，其中E表示没豆，W表示有豆。有三条规则：
4 5 EEWEW EEWEE EWEEE EEEEW
初始化的时候你在左上角，面向右边，而且保证这里没有豆（意思是不存在一个图只有左上角有豆这样不需要动你就赢了嘛）每一次你有两个移动选择，可以往面向的方向走一步也可以往下面走一步，但这样你面向的方向要反过来最后问你吃完所有豆子的最短路径。图的最大格数是150*150。
我们敲代码，就是一把梭。这不是要问最短路吗，BFS写起来麻烦，后面还有两道题呢。那我赶紧写一个DFS试试。
void dfs(int pn, int pm, int dir, int steps, int now) { if(pn >=n || pm >= m) { return; } if(graphs[pn][pm] == 'W') now++; steps++; if(now >=target) { if(steps > answer) answer = steps; return; } if(dir ==0) { dfs(pn,pm-1,0,steps,now); dfs(pn+1,pm,1,steps,now); } else { dfs(pn,pm+1,1,steps,now); dfs(pn+1,pm,-1,steps,now); } }每次历遍一次，要不往当前方向走一步，然后dfs，要不下走一步，转向，继续dfs。结束条件是出了边界，或者吃完所有豆子了。登登登，一提交，过了50%样例，后面的超时了……
这就很懵了。我当时也没想到好的剪枝的方法。也没考虑一下复杂度。之后我找到有人说
通常DFS和BFS复杂度大约均为：系数*状态数^层数 通常此数最多为1亿就八成爆掉
哦，意思是大概是2^150嘛……得，老老实实找规律。
看起来比较简单哈，其实有一个模拟的思想在里面的。根据题意我们可以知道，其实吃豆子是有规律的，每次都必须吃完这一行的才能往下走，而且往下走的时候，还必须满足能吃完下面一行的要求。所以我用pm指示当前豆子位于的列位置，历遍所有行。依据以下步骤： 1. 如果这一行没有豆子，我们就直接跳下一行 2. 先把指针指到能保证吃完这一行的位置（如果面向左边，指针要走到这一行的最右边的豆子那里；如果面向右边，就要走到最左边的豆子那里。），计算需要步数。 3. 吃完这一行（就是如果是面左，就走到最左的豆子那里；反之亦然），计算步数。 4. 走下一行，转方向，重复1
额外情况是，如果都没有豆子，输出0就可以了，根本不用走。这是40%和50
