题目描述
有一块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#include #include 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< <