思维题，一开始看觉得不难，但越想越复杂，弄得想不下去了，然后后来又再想想，就没之前想的那么复杂了。 首先明确几点： 1.割草机只能向“前”走，没法向上或返回走，因此它每到一行，就一定要先把这一行的杂草清除完，才可以准备进入下一行； 2.割草机在奇数行的向“前”意味着向右，在偶数行意味着向左。 每换一行就要换一个方向，好像有点复杂，那能不能转换成每行的方向都一样呢？比如每行都是向右？可以！不过这么做的话，假如你原本的位置在(x,y)，那你换一行后的位置会变为(x+1,y’)，其中y’是y关于[1,m]中点对称的点。
接下来，把整个思路理清： 1.先建图map[n][m]，我们要使割草机在任一行的方向都是向右，那么在奇数行map与原图相同，偶数行map与原图对称。 2.设置r[i]，表示每行最右边的那个’W’的位置，设置low，表示到1~low之间有’W’，遍历一遍map，构造r[i]和low。 3.开始扫图，先把当前行所以的’W’都扫光，扫光后设当前位置为(x,y)，接下来确定“前方” y+1~m对应下一行(x+1,1 ~ y’)的位置有没有’W’（除了第low行外），有的话就记录最右的位置right，继续扫至(x,right)再换行，没有的话直接换行。
代码如下：
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int maxn=155; int n,m; char s[maxn][maxn]; bool map[maxn][maxn]; int r[maxn]={0}; int trans(int y) //对称转换纵坐标 { int mid=(m+1)/2; if(m%2) return 2*mid-y; return 2*mid+1-y; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>s[i]; int low=1; for(int i=1;i<=n;i++) { bool flag=0; for(int j=0;j<m;j++) { if(s[i][j]=='W') { flag=1; map[i][j+1]=1; } else map[i][j+1]=0; } if(flag) low=i; if(i%2==0) { for(int j=1,k=m;j<k;j++,k--) swap(map[i][j],map[i][k]); } for(int j=1;j<=m;j++) if(map[i][j]) r[i]=j; } int cost=0,pos=1; //cost为总消耗时间，pos为当前所在位置的纵坐标 for(int i=1;i<=low;i++) { int j,right=0; for(j=pos+1;j<=r[i];j++) cost++; pos=j-1; if(i==low) break; //已经到了最后一行了，就可以结束 for(j=pos+1;j<=m;j++) { if(map[i+1][trans(j)]) right=j; } for(j=pos+1;j<=right;j++) cost++; if(right) pos=trans(right); else pos=trans(pos); cost++; //换行要+1 } printf("%d\n",cost); return 0; }小结：问题复杂时，可进行转换，一步一步分析，拆成几个步骤
