Wannafly挑战赛4,C

it2022-05-07  7

思维题,一开始看觉得不难,但越想越复杂,弄得想不下去了,然后后来又再想想,就没之前想的那么复杂了。 首先明确几点: 1.割草机只能向“前”走,没法向上或返回走,因此它每到一行,就一定要先把这一行的杂草清除完,才可以准备进入下一行; 2.割草机在奇数行的向“前”意味着向右,在偶数行意味着向左。 每换一行就要换一个方向,好像有点复杂,那能不能转换成每行的方向都一样呢?比如每行都是向右?可以!不过这么做的话,假如你原本的位置在(x,y),那你换一行后的位置会变为(x+1,y’),其中y’是y关于[1,m]中点对称的点。

接下来,把整个思路理清: 1.先建图map[n][m],我们要使割草机在任一行的方向都是向右,那么在奇数行map与原图相同,偶数行map与原图对称。 2.设置r[i],表示每行最右边的那个’W’的位置,设置low,表示到1~low之间有’W’,遍历一遍map,构造r[i]和low。 3.开始扫图,先把当前行所以的’W’都扫光,扫光后设当前位置为(x,y),接下来确定“前方” y+1~m对应下一行(x+1,1 ~ y’)的位置有没有’W’(除了第low行外),有的话就记录最右的位置right,继续扫至(x,right)再换行,没有的话直接换行。

代码如下:

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int maxn=155; int n,m; char s[maxn][maxn]; bool map[maxn][maxn]; int r[maxn]={0}; int trans(int y) //对称转换纵坐标 { int mid=(m+1)/2; if(m%2) return 2*mid-y; return 2*mid+1-y; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>s[i]; int low=1; for(int i=1;i<=n;i++) { bool flag=0; for(int j=0;j<m;j++) { if(s[i][j]=='W') { flag=1; map[i][j+1]=1; } else map[i][j+1]=0; } if(flag) low=i; if(i%2==0) { for(int j=1,k=m;j<k;j++,k--) swap(map[i][j],map[i][k]); } for(int j=1;j<=m;j++) if(map[i][j]) r[i]=j; } int cost=0,pos=1; //cost为总消耗时间,pos为当前所在位置的纵坐标 for(int i=1;i<=low;i++) { int j,right=0; for(j=pos+1;j<=r[i];j++) cost++; pos=j-1; if(i==low) break; //已经到了最后一行了,就可以结束 for(j=pos+1;j<=m;j++) { if(map[i+1][trans(j)]) right=j; } for(j=pos+1;j<=right;j++) cost++; if(right) pos=trans(right); else pos=trans(pos); cost++; //换行要+1 } printf("%d\n",cost); return 0; }

小结:问题复杂时,可进行转换,一步一步分析,拆成几个步骤


最新回复(0)