博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Wannafly挑战赛4 C.割草机 (模拟)
阅读量:5796 次
发布时间:2019-06-18

本文共 1500 字,大约阅读时间需要 5 分钟。

题目描述

有一块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<
<

转载于:https://www.cnblogs.com/orion7/p/7896288.html

你可能感兴趣的文章
利用rand7()构造rand10()
查看>>
MySQL 备份与恢复
查看>>
吃午饭前,按书上的代码写会儿--Hunt the Wumpus第一个版本
查看>>
easyui中combobox的值改变onchang事件
查看>>
TEST
查看>>
PAT A1037
查看>>
ReactiveSwift源码解析(三) Signal代码的基本实现
查看>>
(六)Oracle学习笔记—— 约束
查看>>
[Oracle]如何在Oracle中设置Event
查看>>
top.location.href和localtion.href有什么不同
查看>>
02-创建hibernate工程
查看>>
information_schema系列五(表,触发器,视图,存储过程和函数)
查看>>
瓜子二手车的谎言!
查看>>
[转]使用Git Submodule管理子模块
查看>>
DICOM简介
查看>>
Scrum之 Sprint计划会议
查看>>
List<T> to DataTable
查看>>
[Java]Socket和ServerSocket学习笔记
查看>>
stupid soso spider
查看>>
svn命令在linux下的使用
查看>>