宁波seo网站排名优化公司,电脑用虚拟机做网站,网站域名.xin,北京工程建设公共资源交易平台时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K 64bit IO Format: %lld 题目描述 有一块n*m的地#xff0c;每块地要么长满杂草(用’W’表示)#xff0c;要么是空地(用’G’表示)#xff0c;现在有一个…时间限制C/C 1秒其他语言2秒 空间限制C/C 32768K其他语言65536K 64bit IO Format: %lld 题目描述 有一块n*m的地每块地要么长满杂草(用’W’表示)要么是空地(用’G’表示)现在有一个人站在(1,1)面向(1,m),他可以按如下两种方式移动
1、向面朝的方向移动一格耗费1单位时间
2、向下移动一格并反转面朝的方向(右变左左变右)耗费1单位时间
现在他想知道清除所有的杂草最少需要多少单位时间(清除完杂草之后不用返回(1,1)) 输入描述: 第一行n,m 接下来n行每行一个字符串表示矩阵。 n,m150 输出描述: 一行一个整数表示答案。 示例1 输入
4 5 GWGGW GGWGG GWGGG WGGGG 输出
11 示例2 输入
3 3 GWW WWW WWG 输出
7
分析
这道题开始看想搜索 发现 搜索其中限制条件太多了 每次要判断方向什么的 我们看题意的移动限制 我们发现 只能走两个方向 一个是面朝的方向 另一个是向下走并掉头 那么我们要把行内的杂草都除掉的话 当奇数行也就是只能向右走 那么我们需要至少从奇数行最左边的元素开始走 当偶数行 也就是只能向左走 那么我们需要至少从偶数行最右边的W元素开始扫 所以既然每层的方向固定 那么我们仅需要记录每层最左边和最右边元素的位置 然后每次取定一个移动极限 就够了 然后就是按行扫 记录时间和清除量就可以了
code
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int mod 1e97;
int a[155][155];
int rn[155],rm[155];
int main()
{int n,m;int c0;scanf(%d%d ,n,m);for(int i1;in;i){rn[i] 200;for(int j1;jm;j){scanf(%c,a[i][j]);if(a[i][j]W){c;rm[i] max(rm[i],j);//记录当前行的W的最左和最右rn[i] min(rn[i],j); }} getchar();}int clear0;int x1,y1,lim,t0;for(x1;clear!c;x,t){if(x%2){// right directionif(xn)lim rm[x];else lim max(rm[x1],rm[x]);while(ylim){if(a[x][y]W)clear;y;t;}if(a[x][y]W)clear;}else{if(xn)lim rn[x];else lim min(rn[x1],rn[x]);while(ylim){if(a[x][y]W)clear;y--;t;}if(a[x][y]W)clear;}if(clearc)break;}printf(%d\n,t);return 0;
}
