题目描述
有一块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
样例1输出
11
示例2输入
3 3 GWW WWW WWG
样例2输出
7
分析: 小明割草只有两个方向 向右和向左,并且奇数行时他是从左向右进行割草的,偶数行它是从右往左割草的.
当从奇数行向下进入偶数行时,要从这两行中草的最大纵坐标处下去;当从偶数行割到奇数行时,要从这两行中最小的纵坐标处下去;
然后进行模拟即可
参考代码:
// #include<bits/stdc++.h> using namespace std; int g[200][3];//arr[]:记录每一行的草地 g:记录每行草地最左边和最右边的位置 char arr[200]; string str; int n,m,last,end1,res,start;//last:最后一行的位置 int main() { cin>>n>>m; for(int i = 1; i <=n+1; i++) { g[i][1] = 200;//g[i][] 初始化 g[i][2] = -100; } for(int i = 1; i <= n; i++) { memset(arr,'0',sizeof(arr)); scanf("%s",arr+1); //cin>>str; for(int j = 1; j<=m; j++) { if(arr[j]=='W') { if(j<g[i][1]) { //寻找该行草在最左边出现的位置 g[i][1] = j; } if(j>g[i][2]) { //寻找该行草在最右边出现的位置 g[i][2] = j; } last = i;//存放最后一行. } } } // 开始割草 start = 1;//从哪个位置开始割草 初始为1 for(int i = 1; i <= last; i++) { if(i%2) { //>0 奇数行 end1 = max(g[i][2],g[i+1][2]); if(end1-start>0 ) { res += (end1-start); start = end1; } } else { //偶数行 end1 = min(g[i][1],g[i+1][1]); if((start - end1) > 0 ) { res += (start - end1); start = end1; } } } cout<<res+last-1<<endl; return 0; } //4 4 //GGWW //GGGG //GGGG //WWWW //3 4 //GGWW //GGGG //WWWW //11
