题目描述
有一块n*m的地，每块地要么长满杂草(用'W'表示)，要么是空地(用'G'表示)，现在有一个人站在(1,1)，面向(1,m),他可以按如下两种方式移动：
1、向面朝的方向移动一格，耗费1单位时间
2、向下移动一格，并反转面朝的方向(右变左，左变右)，耗费1单位时间
现在他想知道清除所有的杂草最少需要多少单位时间(清除完杂草之后不用返回(1,1))
输入描述:
第一行n,m
接下来n行每行一个字符串表示矩阵。
n,m<=150
输出描述:
一行一个整数表示答案。
示例1
输入
4 5
GWGGW
GGWGG
GWGGG
WGGGG
输出
11
示例2
输入
3 3
GWW
WWW
WWG
输出
7
题意：
题解：
有几种情况需要考虑。中间都是空行的时候， 当后面都是空行就不需要移动了。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
char maze[200][200];
const int INF=0x3f3f3f3f;
int lft[200];
int rht[200];
int main()
{
while(cin>>n>>m)
{
memset(lft,INF,sizeof(lft));//需要移动到的最左边
memset(rht,0,sizeof(rht));//最右边
int last=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>maze[i][j];
if(maze[i][j]=='W')
{
last=i;
lft[i]=min(lft[i],j);
rht[i]=max(rht[i],j);
}
}
}
int ans=0;
int cur=1;//起始位置
for(int i=1;i<=last;i++)
{
int next;
if(i%2)
{
next=max(rht[i],rht[i+1]);
if(next-cur>0)
ans+=next-cur,cur=next;
}
else
{
next=min(lft[i],lft[i+1]);
if(cur-next>0)
ans+=cur-next,cur=next;
}
}
cout<<ans+last-1<<endl;
}
return 0;
}