Lawnmower

Lawnmower
题面





题意
按照题干中的四种方式走，只要向下走一行，方向就会转变，问最少走的步数能够除掉所有的草。
Note
开始的位置在（1,1）

分析
这道题就是贪心+模拟，但是这道题细枝末节非常多，我再这个坑上wa了2-3次。接下来我就先讲坑再讲思路
坑

1.走到某一行的时候发现已经没有杂草了，但是程序还是接着跑直到跑完所有行。
solution:我们开始的时候重置n，就是我们从第1、2、3…搜到第n行，如果发现第m行开始到第n行没有任何杂草，我们就可以直接让n变成m即可
2.明确一点：我的思路是先把每一行的第一颗杂草的列坐标与最后一颗杂草的列坐标存在结构体数组里面

struct{
int x;//x表示第一颗杂草的列坐标
int y;//y表示最后一颗杂草的列坐标
}b[105]//b[1]表示第一行

3.我们发现中间某一些行是无杂草的
solution我们在当前行的时候判断一下下面一行的第一颗杂草的列坐标与最后一颗杂草的列坐标，看一下是否结果都是0.如果都是0的话就表明下一行无杂草。按照我们人的思维，接下来肯定是把当前行的杂草除完，一旦在某一个位置除完，我们就可以直接往下一行走了。那我们在代码上就可以把下一行的x与y全部调成除完当前行的位置

for(i=1;i<rn;i++){
	**if(i%2){
		if(b[i+1].x==0&&b[i+1].y==0){
			b[i+1].x=b[i+1].y=b[i].y;
		}**//重点操作
		num=max(b[i].y,b[i+1].y);
		d=d+num-start+1;
		start=num;
	}
	else{
		**if(b[i+1].x==0&&b[i+1].y==0){
			b[i+1].x=b[i+1].y=b[i].x;
		}**//重点操作
		num=min(b[i].x,b[i+1].x);
		d=d+start-num+1;
		start=num;
	}
	/*printf("i=%d d=%d\n",i,d);*/

}

4.经过第三行操作，第2行到第n行的x与y都不是0，接下来坑就是第一行可能会存在x与y为0。这里就要特别提醒一下，第一行的x与y会对第二行有影响当且仅当第二行x与y都是0。这时我们就可以来一个特判

if(b[1].x==0&&b[1].y==0&&b[2].x==0&&b[2].y==0) {b[2].x=b[2].y=1;}

除了这个操作其实还有其他操作也可以实现这个功能，比如说只要把第一行的x与y同时改变即可

坑点就是这么多了

思路

for(i=1;i<rn;i++){
	if(i%2){
		if(b[i+1].x==0&&b[i+1].y==0){
			b[i+1].x=b[i+1].y=b[i].y;
		}
		num=max(b[i].y,b[i+1].y);
		d=d+num-start+1;
		start=num;
	}
	else{
		if(b[i+1].x==0&&b[i+1].y==0){
			b[i+1].x=b[i+1].y=b[i].x;
		}
		num=min(b[i].x,b[i+1].x);
		d=d+start-num+1;
		start=num;
	}
	/*printf("i=%d d=%d\n",i,d);*/

}
/*printf("rn=%d\n",rn);*/
if(i==rn){
	if(rn%2==0){
		if(b[i].x)
		d=d+start-b[i].x;
	}//向左移动
	else{
		if(b[i].y)
		d=d+b[i].y-start;
	}
}

我们以两行为单位即1-2 2-3 3-4…
这样最后一行肯定是单独处理，对于上面两行我们该如何处理呢？
首先start表示在每一行的位置的初始位置，num表示每一行需要到达的位置。所以对于一个单位，我们需要确定两个值，一个就是start，另一个就是num。对于start就是上一行的num，所以我只要讲一下num怎么用代码实现就可以了。首先处理的行要分奇数与偶数，奇数表示人朝右，那么我们就要比较下一行的y与这一行的y，找到最大值就是num的值。偶数表示人朝左，那我们就要比较下一行与这一行的x，找到最小值就是num的值。
别忘了操作完毕之后，就要把num赋值给start.
最后一行处理，其实很简单看它朝那一个方向，然后计算就可以了。

AC代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n,m,ed;
char a[155][155];
struct{
int x;
int y;
}b[155];
int Search(int q){
   for(int i=q;i<=n;i++){
	for(int j=1;j<=m;j++){
		if(a[i][j]=='W') return 0;
	}
   }
   return 1;
}
int main(){
int d=0,start=1,num,i,rn,j;
cin>>n>>m;
for(i=1;i<=n;i++){
	scanf("%s",a[i]+1);
}
for(i=1;i<=n;i++){
	int cnt=0;
	for(j=1;j<=m;j++){
	if(!cnt&&a[i][j]=='W'){
		cnt=1;
		b[i].x=j;
	}
	if(a[i][j]=='W') b[i].y=j;
	}
}
/*for(int i=1;i<=n;i++){ cout<<"起点是"<<b[i].x<<' '<<"终点是"<<b[i].y<<endl; }*/
for(i=1;i<=n;i++){
/* printf("i=%d Search(%d)=%d\n",i,i,Search(i));*/
	if(Search(i)) {rn=i-1;break;}
}
/*printf("rn=%d\n",rn);*/
if(i==n+1) rn=n;
if(b[1].x==0&&b[1].y==0&&b[2].x==0&&b[2].y==0) {b[2].x=b[2].y=1;}
for(i=1;i<rn;i++){
	if(i%2){
		if(b[i+1].x==0&&b[i+1].y==0){
			b[i+1].x=b[i+1].y=b[i].y;
		}
		num=max(b[i].y,b[i+1].y);
		d=d+num-start+1;
		start=num;
	}
	else{
		if(b[i+1].x==0&&b[i+1].y==0){
			b[i+1].x=b[i+1].y=b[i].x;
		}
		num=min(b[i].x,b[i+1].x);
		d=d+start-num+1;
		start=num;
	}
	/*printf("i=%d d=%d\n",i,d);*/

}
/*printf("rn=%d\n",rn);*/
if(i==rn){
	if(rn%2==0){
		if(b[i].x)
		d=d+start-b[i].x;
	}//向左移动
	else{
		if(b[i].y)
		d=d+b[i].y-start;
	}
}
cout<<d<<endl;
  return 0;
}